几年没写题解来更一篇。 首先有一个规律就是如果满足条件那么 gcd(y,k)=1 那么答案就是 ∑i=1n∑j=1m[gcd(i,j)=1][gcd(j,k)=1] =∑j=1m[gcd(j,k)=1]∑i=1n∑t|i,t|jμ(t) =∑t=1mμ(t)∗⌊nt⌋∑j=1mt[gcd(tj,k)=1] ==∑t=1mμ(t)∗⌊⌊nt⌋⌋[gcd(t,k)=1]∑j=1⌊mt⌋[gcd(j,k)=1] O(n√) 枚举 ⌊nt⌋,⌊mt⌋ 对于每段 ∑j=1x[gcd(j,k)=1]=∑r|kμ(r)∗⌊xr⌋ 直接算就行了。 设k的质因数分解为 pa11pa22....pacntcnt ， ki=pa11pa22....paii 设 f(i,x)=∑t=1xμ(t)[gcd(t,ki)=1] 那么要求的是 f(cnt,x) f(i,x)=∑t=1xμ(t)[gcd(t,ki)=1] =∑t=1xμ(t)[gcd(t,ki−1paii)=1] =∑t=1xμ(t)[gcd(t,ki−1)=1][gcd(t,pi)=1] =∑t=1xμ(t)[gcd(t,ki−1)=1]−∑pi|tμ(t)[gcd(t,ki−1)=1] =∑t=1xμ(t)[gcd(t,ki−1)=1]−∑t=1⌊xpi⌋μ(t∗pi)[gcd(t∗pi,ki−1)=1] =∑t=1xμ(t)[gcd(t,ki−1)=1]−∑t=1⌊xpi⌋μ(t∗pi)[gcd(t,ki)=1] 然后第二段中如果 t%pi=0 没有贡献，否则当 gcd(t,pi)=1 时 μ(t∗pi)=−μ(t) 因此上式 =∑t=1xμ(t)[gcd(t,ki−1)=1]+∑t=1⌊xpi⌋μ(t)[gcd(t,ki)=1] =f(i−1,x)+f(i,⌊xpi⌋) 当 i=0 时 f(i,x) 可以通过杜教筛计算。 然后这个杜教筛就是把 ∑i=1⌊nx⌋μ(i) 算一遍。 因此复杂度大概是 O(min(n,m)−−−−−−−−√∗(k√+logn)+n23logn)
Orz 小火车
#include <bits/stdc++.h> using namespace std; #define N 5100000 #define A 5000000 #define ll long long ll ans; int n,m,K,cnt,cnt1; int mu[N],prime[N],ip[N],sum[N],p[11],p1[110]; map<pair<int,int>,int>ma1; map<int,int>ma2; void init() { mu[1]=1; for(int i=2;i<=A;i++) { if(!ip[i]){prime[++cnt]=i;mu[i]=-1;} for(int j=1;j<=cnt&&i*prime[j]<=A;j++) { ip[i*prime[j]]=1; if(i%prime[j]==0)break; mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=A;i++) sum[i]=sum[i-1]+mu[i]; cnt=0; for(int i=1;i<=K;i++) if(K%i==0)p1[++cnt1]=i; for(int i=1;prime[i]<=K;i++) if(K%prime[i]==0)p[++cnt]=prime[i]; } int djs(int x) { if(x<=A)return sum[x]; if(ma2.count(x))return ma2[x]; int ret=1; for(int i=2,last;i<=x;i=last+1) { last=x/(x/i); ret-=djs(x/i)*(last-i+1); } return ma2[x]=ret; } int cal1(int x,int y) { if(y==0)return 0; if(x==0)return djs(y); pair<int,int> t=make_pair(x,y); if(ma1.count(t))return ma1[t]; int ret=cal1(x-1,y)+cal1(x,y/p[x]); return ma1[t]=ret; } int cal2(int x) { int ret=0; for(int i=1;i<=cnt1;i++) ret+=mu[p1[i]]*(x/p1[i]); return ret; } int main() { scanf("%d%d%d",&n,&m,&K); init(); for(int i=1,last;i<=m&&i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); ans+=(ll)(cal1(cnt,last)-cal1(cnt,i-1))*(n/i)*cal2(m/i); } printf("%lld\n",ans); return 0; }