NOI2016 循环之美
复习莫比乌斯反演...
- 需要/可能用到的知识点：
[[iot j]=sum_{d|gcd(i,j)} mu(d)=sum_{d|i,d|j}mu(d)
]
[forall iot j,mu(ij)=mu(i)mu(j)
]
[forall i
ot ot j,mu(ij)=0
]
-
杜教筛相关
[g(1) S(n)=sum_{i=1}^{n}(f * g)(i)-sum_{i=2}^{n} g(i) Sleft(leftlfloorfrac{n}{i} ight floor ight) ]ll GetSum(int n) { // 算 f 前缀和的函数 ll ans = f_g_sum(n); // 算 f * g 的前缀和 // 以下这个 for 循环是数论分块 for(ll l = 2, r; l <= n; l = r + 1) { // 注意从 2 开始 r = (n / (n / l)); ans -= (g_sum(r) - g_sum(l - 1)) * GetSum(n / l); // g_sum 是 g 的前缀和 // 递归 GetSum 求解 } return ans; }然后我们先筛出前(n^frac 2 3)个答案，总复杂度(n^{frac 2 3})
然后做推式子题的时候注意函数本身的性质、计算顺序、能否递归等
这题推出来的式子是
[sum_{d=1}^n[dot k]mu(d)leftlfloorfrac n d
ight
floor sum_{j=1}^{m/d}[jot k]
]
然后要算这两个的前缀和
[f(n)=sum_{i=1}^n[iot k]\S(n)=sum_{i=1}^n[iot k]mu(i)
]
相当于被分成了k段，这k段的f都是相同的，然后单独考虑最后一段
所以
[f(n)=leftlfloorfrac n k
ight
floor f(k)+f(x ext{%} k)
]
预处理出k以内的值就好了
对于第二个，
[S(n,k)=sum_{i=1}^n [iot k]|mu(i)\=sum_{i=1}^n mu(i)sum_{d|i,d|k}mu(d)
]
[=sum_{d|k}mu(d)sum_{d|i}mu(i)
]
[=sum_{d|k}mu(d)sum_{i=1}^{x/d}mu(id)
]
[=sum_{d|k}mu(d)sum_{i=1,iot d}^{x/d}mu(i)mu(d)
]
[=sum_{d|k}mu^2(d)sum_{i=1}^{x/d}[iot d]mu(i)
]
[=sum_{d|k}mu^2(d)S(leftlfloorfrac x d
ight
floor,d)
]
边界：(g(n,1)=sum_{i=1}^n mu(i))，杜教筛即可。
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
int read(){
int x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
const int N =2e6;
int n,m,k;
int np[N],mu[N],f[N],pri[N],tot,sm[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
void init(){
mu[1]=1;
FOR(i,1,2000) f[i]=f[i-1]+(gcd(i,k)==1);
FOR(i,2,N-1){
if(!np[i]) pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&pri[j]*i<N;j++){
int now=i*pri[j];np[now]=1;
if(i%pri[j]==0){
mu[now]=0;break;
}else mu[now]=mu[i]*-1;
}
}
FOR(i,1,N-1) sm[i]=sm[i-1]+mu[i];
}
ll F(int now){
return now/k*f[k]+f[now%k];
}
#define pbl pair<bool,ll>
#define mp make_pair
struct node{
int key1,key2;ll res;int nex;
};
pbl nq;
struct hash_table{
int head[20000001];node edge[20000001];
int top=0;
int hash(int k1,int k2){
return (1ll*abs(k1)*9982443537+abs(k2))%20000000;
}
void add(int u,int k1,int k2,ll w){
edge[++top].res=w;
edge[top].key1=k1;
edge[top].key2=k2;
edge[top].nex=head[u];
head[u]=top;
}
void insert(int k1,int k2,ll w){
int u=hash(k1,k2);
add(u,k1,k2,w);
}
void count(int k1,int k2){
int u=hash(k1,k2);
for(int i=head[u];i;i=edge[i].nex){
if(edge[i].key1==k1&&edge[i].key2==k2) return nq=mp(1,edge[i].res),void();
}
nq=mp(0,0);return;
}
}M;
ll S(int now,int k){
if(!now||(k==1&&now<N)) return sm[now];
M.count(now,k);
if(nq.first) return nq.second;
ll res=0;
if(k==1){
res=1;
for(ll l=2,r;l<=now;l=r+1){
r=now/(now/l);
res-=(r-l+1)*(S(now/l,1));
}
}else{
for(int i=1;i*i<=k;i++){
if(k%i) continue;
if(mu[i]) res+=S(now/i,i);
if(mu[k/i]&&i!=k/i) res+=S(now/(k/i),k/i);
}
}
return M.insert(now,k,res),res;
}
int main(){
n=read(),m=read(),k=read();
init();int pre=0;int r;
ll ans=0;
for(int l=1;l<=min(n,m);l=r+1){
r=min((n/(n/l)),(m/(m/l)));
int now=S(r,k);
ans+=1ll*(now-pre)*(n/l)*F(m/l);
pre=now;
}
printf("%lld",ans);
return 0;
}