C++14(g++5.4) 解法, 执行用时: 863ms, 内存消耗: 83800K, 提交时间: 2019-06-24 17:07:56

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
#define MAXN 4000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int M,N;
int f[MAXN],prime[MAXN],tot,phi[MAXN];
int h[MAXN],bl[2005],br[2005],id[MAXN],cnt,lz[2005];
int sum[MAXN];
bool nonprime[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a % b);
}
int main(){
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    read(M);read(N);
    phi[1] = 1;
    h[1] = 1;
    for(int i = 2 ; i <= N ; ++i) {
	if(!nonprime[i]) {
	    prime[++tot] = i;
	    phi[i] = i - 1;
	}
	for(int j = 1 ; j <= tot ; ++j) {
	    if(prime[j] > N / i) break;
	    nonprime[i * prime[j]] = 1;
	    if(i % prime[j] == 0) {
		phi[i * prime[j]] = phi[i] * prime[j];
		break;
	    }
	    else {
		phi[i * prime[j]] = phi[i] * phi[prime[j]];
	    }
	}
	h[i] = mul(phi[i],mul(i,i));
	update(h[i],h[i - 1]);
    }
    for(int i = 1 ; i <= N ; ++i) {
	sum[i] = mul(i,i);
	f[i] = mul(i,i);
	update(sum[i],sum[i - 1]);
    }
    int S = sqrt(N);
    for(int i = 1 ; i <= N ; ++i) {
	int r = min(N,i + S - 1);
	++cnt;
	bl[cnt] = i;br[cnt] = r;i = r;
	for(int j = bl[cnt] ; j <= br[cnt] ; ++j) id[j] = cnt;
    }
    int a,b,k;
    int64 x;
    for(int i = 1 ; i <= M ; ++i) {
	read(a);read(b);read(x);read(k);
    int g = gcd(a,b);
	int d = (x / (1LL * a / g * b / g)) % MOD;
	int c = inc(d,MOD - f[g]);
	f[g] = d;
	for(int j = g ; j <= br[id[g]] ; ++j) {
	    update(sum[j],c);
	    
	}
	for(int j = id[g] + 1 ; j <= cnt ; ++j) update(lz[j],c);
	int res = 0;
	for(int j = 1 ; j <= k ; ++j) {
	    int r = k / (k / j);
	    int s = inc(sum[r],lz[id[r]]);
	    s = inc(s,MOD - inc(sum[j - 1],lz[id[j - 1]]));
	    update(res,mul(s,h[k / j]));
	    j = r;
	}
	out(res);enter;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1429ms, 内存消耗: 64160K, 提交时间: 2020-08-25 20:49:08

#include<cstdio>
#define N 4000005
#define mod 1000000007
using namespace std;
int c[N],n,p[N],v[N],phi[N],f[N];
void inc(int i,int x){for(;i<=n;i+=-i&i)c[i]=(c[i]+x)%mod;}
int query(int i){
	int ans=0;
	for(;i;i-=-i&i)ans=(ans+c[i])%mod;
	return ans;
}
int gcd(int a,int b){
	int r=a%b;
	while(r)a=b,b=r,r=a%b;
	return b;
}
int qp(int a,int x){
	int i=1;
	for(;x;x/=2,a=1ll*a*a%mod)if(x&1)i=1ll*i*a%mod;
	return i;
}
int main(){
	int m,i,j,w,k;long long x;
	//freopen("input.in","r",stdin);
	scanf("%d%d",&m,&n);
	for(i=v[phi[1]=1]=2;i<=n;i++){
		if(!v[i])phi[v[i]=p[++p[0]]=i]=i-1;
		for(j=1;j<=p[0]&&i*p[j]<=n;j++){
			v[i*p[j]]=1;
			if(i%p[j])phi[i*p[j]]=phi[i]*(p[j]-1);
			else{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
		}
	}
	for(i=1;i<=n;i++){
		phi[i]=(1ll*i*i%mod*phi[i]%mod+phi[i-1])%mod;
		inc(i,f[i]=1ll*i*i%mod);
	}
	while(m--){
		scanf("%d%d%lld%d",&i,&j,&x,&k);
		w=gcd(i,j);
		x=1ll*w*w%mod*(x%mod)%mod*qp(1ll*i*j%mod,mod-2)%mod;
		inc(w,(x-f[w]+mod)%mod);f[w]=x;
		for(i=1,w=0;i<=k;i=j+1){
			j=k/(k/i);
			w=(w+1ll*phi[k/i]*(query(j)-query(i-1))%mod)%mod;
		}
		printf("%d\n",(w+mod)%mod);
	}
	return 0;
}