Codeforces915G. Coprime Arrays

n<=2e6的数组，m<=2e6个询问，对1<=i<=m的每个i问：只用<=i的数字填进数组，有多少种方案使数组的总gcd=1.强制把每个询问的答案求出来。

比如说现在有个确定的i=t，然后看看答案怎么算先。先把所有情况加起来，然后除去gcd=2，3，4，5，……的，那直接统计有多少gcd=2，3，4，5的不方便，总可以统计有多少gcd是2的倍数的，3的倍数的，……，吧！这样的话丢掉了gcd为2的倍数，3的倍数的，等等6的倍数丢多了一次因为在2和3都算了，要减掉……就一个容斥，对应了各自的莫比乌斯函数。于是可以愉快的写出t的答案$f(t)=\sum_{i=1}^{t} \mu(i) (\frac{t}{i})^n$。

然后就看看t变成t+1时答案怎么变化，对一个k，他的$(\frac{t}{k})$只有在t是k的倍数时才会变化！而这个“变化”的总数，就是1-m中所有1-m的倍数的数量的总数，就是m+m/2+m/3+……，就是mlnm个“变化”，就可以做！

 #include<string.h>

 #include<stdlib.h>

 #include<stdio.h>

 #include<math.h>

 //#include<assert.h>

 #include<algorithm>

 //#include<iostream>

 //#include<bitset>

 using namespace std;

 int n,m;

 #define maxn 2000011

 const int mod=1e9+;

 int miu[maxn],prime[maxn],lp=,mi[maxn],small[maxn]; bool notprime[maxn];

 int powmod(int a,int b)

 {

     int ans=;

     while (b)

     {

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

         a=1ll*a*a%mod;

         b>>=;

     }

     return ans;

 }

 void pre(int n)

 {

     miu[]=;

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

     {

         if (!notprime[i]) {prime[++lp]=i; miu[i]=-; small[i]=i;}

         for (int j=;j<=lp && 1ll*prime[j]*i<=n;j++)

         {

             notprime[i*prime[j]]=;

             small[i*prime[j]]=prime[j];

             if (i%prime[j]) miu[i*prime[j]]=-miu[i];

             else {miu[i*prime[j]]=; break;}

         }

     }

 }

 int ans,fix,num[maxn];

 int list[maxn],ci[maxn],ll;

 void play(int x)

 {

     fix+=miu[x]*(mi[num[x]+]-mi[num[x]]);

     fix+=fix<?mod:,fix-=fix>=mod?mod:;

     num[x]++;

 }

 void dfs(int now,int cur)

 {

     if (cur>ll) {play(now); return;}

     for (int i=,tmp=;i<=ci[cur];i++,tmp*=list[cur]) dfs(now*tmp,cur+);

 }

 void solve(int x)

 {

     ll=;

     for (int i=x;i>;i/=small[i])

     {

         if (list[ll]!=small[i]) list[++ll]=small[i],ci[ll]=;

         else ci[ll]++;

     }

     dfs(,);

 }

 int main()

 {

     scanf("%d%d",&n,&m); pre(m);

     for (int i=;i<=m;i++) mi[i]=powmod(i,n);

     ans=; fix=;

     for (int i=;i<=m;i++) solve(i),ans+=i^fix,ans-=ans>=mod?mod:;

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

     return ;

 }

巴特西

Codeforces915G. Coprime Arrays

最新文章

热门文章