P4863 JerryC Loves Driving

2018-09-05 16:56:15


这题是真的难受。。想了两个小时还是看了题解

首先一看这个式子和数据范围,可能是个数论

别急,先打个表看看有没有什么规律

打出 $A,B∈[1,15]$ 的所有解后,我发现对角线好像有点奇妙

然后用了一个小时去探索对角线的奥秘

不出所料,并没有可行的规律

咋办呢?看看题解咋做的

诶他也打了个表?诶他这个表怎么和我的不一样?

题解打的不是答案的表,是求和的每一项

原来规律在这

发现对于第i列,从上到下是连续的自然数,每个自然数重复i次

我们要求和的是第A行到第B行,第1列到第B列

所以直接枚举列求和即可,时间复杂度 $O(B)$

注意开 $long long$

我不爱找规律了 心情简单.jpg

从这道题确实可以得出一个结论

答案没有规律的时候不妨换一种思路,看一看求和的各项有没有规律

如果总是挂在找规律上岂不是肥肠丢人

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a,b;
ll ans;
inline ll sum(int n){return 1ll*n*(n+1)/2;}
int main()
{
    scanf("%d%d",&a,&b);
    for (int i=1;i<=b;i++)
    {
        ll t=(i&1)?-1:1;
        int x=a/i,y=b/i,c=a%i,d=b%i;
        ll ans1=1ll*x*(i-c)*t,ans2=1ll*y*(d+1)*t;
        ans+=ans1+ans2+1ll*(sum(y-1)-sum(x))*i*t;
    }
    printf("%lld\n",ans);
    return 0;
}