传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4818 思路： 看到这道题我就想到当年noip模拟赛T1 是一个伪装的”很好”的辗转相除而我做了半天的悲惨经历。。感动的落泪。 首先注意到那个规则就是辗转相除，不过不是标准形式，化成标准形式后多迭代几次很容易发现性质： f(a,b)=a∗bgcd(a,b)2∗f(gcd(a,b),gcd(a,b)) 这个通过归纳法也很容易证明 这样ans = ∑ki=1∑kj=1f(i,j) 化简这个式子，注意到一个经典问题： ∑ni=1[(i,n)=1]i=n∗(φ+e)2 利用这个我们的式子变成了： ∑ni=1f(i,i)∗g(⌊ni⌋) 其中 g(n)=∑ni=1i∗i∗ϕ(i) 可以做到线性预处理 g 那么暴力维护修改的话就是套一个bit,明显T飞了。。。 到这里就非常像我bzoj 3529的做法了，一道披着数论外衣的数据结构狼？ 注意到修改和查询是不均衡的，用序列分块就可以解决了， 这样就能做到O(1)查询， O(n√)修改 ，总的复杂度: O(m∗n√) 另外按bzoj 3529那个题的做法我们也可以用定期重构的分块解决这个问题，这不过这里因为 n 很大的原因，重构次数不能太多，我估计在5次左右就可以了。。。应该也是可以通过的吧。 感觉自己基础差的要死。。。一开始连φ都筛错了半天没看出来，难怪滚粗呢QAQ
代码（分块）：
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<cmath> #define N 4000002 using namespace std; typedef long long LL; LL n,m,phi[N],g[N],now[N]; const LL P = 1000000007LL; inline void in(LL &x) { char c; while (!isdigit(c = getchar())); x = (c ^ 48); while (isdigit(c = getchar())) x = 10 * x + (c ^ 48); } inline LL gcd(LL a,LL b) { return (!b) ? (a) : gcd(b,a % b); } inline void inc(LL &x,LL y) { x += y; if (x >= P) x -= P; } int cnt,prime[N]; bool not_prime[N]; inline void Sieve() { memset(not_prime,0,sizeof(not_prime)); cnt = 0; phi[1] = 1; for (int i = 2;i <= n; ++i) { if (!not_prime[i]) { prime[++cnt] = i; phi[i] = i - 1; } for (int j = 1;j <= cnt; ++j) if (prime[j] * i > n) break; else { not_prime[prime[j] * i] = 1; if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1); else { phi[i * prime[j]] = phi[i] * prime[j]; break; } } } g[0] = 0; for (int i = 1;i <= n; ++i) g[i] = (g[i - 1] + 1LL * i * i % P * phi[i] % P) % P; } LL S[N]; int num,belong[N],lb[N],rb[N],B; inline void Divide() { B = (int)(sqrt(n)) ; for (int i = 1;i <= n; ++i) belong[i] = (i - 1) / B + 1; belong[0] = belong[n + 1] = -1; for (int i = 1;i <= n; ++i) { if (belong[i] != belong[i - 1]) lb[belong[i]] = i; if (belong[i] != belong[i + 1]) rb[belong[i]] = i; } num = belong[n]; for (int i = 1;i <= num; ++i) { int le = lb[i],re = rb[i]; S[le] = now[le] % P; for (int j = le + 1;j <= re; ++j) S[j] = (S[j - 1] + now[j]) % P; } } inline void Pre() { for (int i = 1;i <= n; ++i) now[i] = 1LL * i * i; Sieve(); Divide(); } inline void init() { in(m); in(n); Pre(); } inline void change(LL a,LL b,LL x,LL k) { LL last,GCD = gcd(a,b),delta; last = now[GCD]; now[GCD] = x / (a * b / (GCD * GCD)); delta = (now[GCD] - last) % P; if (delta < 0) delta += P; int re = rb[belong[GCD]]; for (int i = GCD;i <= re; ++i) inc(S[i],delta); } LL ans; inline LL GET(LL l,LL r) { int ll = belong[l],rr = belong[r]; LL Sum = 0; if (ll == rr) { if (l == lb[ll]) inc(Sum,S[r]); else inc(Sum,(S[r] - S[l - 1] + P) % P); return Sum; } Sum = S[r]; if (l == lb[ll]) inc(Sum,S[rb[ll]]); else inc(Sum,(S[rb[ll]] - S[l - 1] + P) % P); for (int i = ll + 1;i < rr; ++i) inc(Sum,S[rb[i]]); return Sum; } inline void Query(LL a,LL b,LL x,LL k) { ans = 0; for (int i = 1,j;i <= k;i = j + 1) { j = k / (k / i); inc(ans,g[k / i] * GET(i,j) % P); } printf("%lld\n",ans); } LL a,b,x,k; inline void DO_IT() { for (int i = 1;i <= m; ++i) { in(a); in(b); in(x); in(k); change(a,b,x,k); Query(a,b,x,k); } } int main() { init(); DO_IT(); return 0; }