bzoj 4815: [Cqoi2017]小Q的表格 [数论]

4815: [Cqoi2017]小Q的表格

题意：

单点修改，查询前缀正方形和。修改后要求满足条件f(a,b)=f(b,a), b×f(a,a+b)=(a+b)*f(a,b)

一开始sb了认为一次只会改动两三个格子想了个cdq分治做法...

一次会影响很多格子...

经过观察以及\((a,b)=(a,a-b)=(a,a+b)\)发现，每次修改影响所有\((i,j)=(a,b)\)的点对，并且关系为\(f(i,j)=\frac{i}{a}\frac{j}{b} f(a,b)\)

我们可以只记录\(f(d,d)\)的值\(f(d)\)，其他值都能得到

然后套路推倒，最后得到

这里用莫比乌斯反演我只会两个分块，不如直接代入phi

维护f值可以用分块，总体复杂度\(O(n\sqrt{n})\)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 4e6+5, mo = 1e9+7, M = 3e3+5, inv2 = (mo+1)/2;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

    return x*f;

}

bool notp[N]; int p[N/10], phi[N]; ll s[N];

void sieve(int n) {

	phi[1] = 1;

	for(int i=2; i<=n; i++) {

		if(!notp[i]) p[++p[0]] = i, phi[i] = i-1;

		for(int j=1; j <= p[0] && i*p[j] <= n; j++) {

			notp[i*p[j]] = 1;

			if(i%p[j] == 0) {

				phi[i*p[j]] = phi[i] * p[j];

				break;

			}

			phi[i*p[j]] = phi[i] * (p[j] - 1);

		}

	}

	for(int i=1; i<=n; i++) s[i] = (s[i-1] + (ll) i * i %mo * phi[i] %mo) %mo;

}

int gcd(int a, int b) {return !b ? a : gcd(b, a%b);}

ll Pow(ll a, int b) {

	ll ans=1;

	for(; b; b>>=1, a=a*a%mo)

		if(b&1) ans=ans*a%mo;

	return ans;

}

int Q, n, a, b, k; ll x;

namespace B {

	int f[N], add[N], a[N];

	int pos[N], block, m;

	struct _blo{int l, r;} b[N];

	void init() {

		block = sqrt(n); m = (n-1)/block+1;

		for(int i=1; i<=n; i++) pos[i] = (i-1)/block+1, a[i] = (ll)i*i%mo, f[i] = (a[i] + f[i-1]) %mo;

		for(int i=1; i<=m; i++) b[i].l = (i-1)*block+1, b[i].r = i*block;

	}

	int que(int x) { return (f[x] + add[pos[x]]) %mo; }

	void cha(int x, int v) {

		int d = (v - a[x] + mo) %mo, r = b[pos[x]].r; a[x] = v;

		if(d==0) return;

		for(int i=x; i<=r; i++) f[i] = (f[i] + d) %mo;

		for(int i=pos[x]+1; i<=m; i++) add[i] = (add[i] + d) %mo;

	}

} using B::cha; using B::que;

void solve(int n) {

	int ans = 0, r, last = 0, now;

	for(int i=1; i<=n; i=r+1, last=now) {

		r = n/(n/i); now = que(r);

		ans = (ans + (ll) (now - last + mo) * s[n/i] %mo) %mo;

	}

	printf("%d\n", (ans + mo) %mo);

}

int main() {

	freopen("in", "r", stdin);

	Q=read(); n=read();

	sieve(n);

	B::init();

	for(int i=1; i<=Q; i++) {

		a=read(); b=read(); scanf("%lld", &x); k=read();

		x %= mo;

		int d = gcd(a, b);

		cha(d, (ll) d * d %mo * x %mo * Pow((ll) a * b %mo, mo-2) %mo );

		solve(k);

	}

}