P4863 JerryC Loves Driving

这题是真的难受。。想了两个小时还是看了题解 首先一看这个式子和数据范围，可能是个数论 别急，先打个表看看有没有什么规律 打出$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; } ```