T66099 小xzy的数对

题目背景

老师带同学参加表演，要求学生两两一组表演，但有些学生一起会发生冲突，现在老师想知道有多少组学生分到一起时不会发生冲突。

题目描述

学生发生冲突当且仅当他们身上的编号有大于1的公因数。学生身上的编号是1~n。输入n，输出有多少组学生分到一起时不会发生冲突。

我们认定11与任何数都互质。

输入输出格式

输入格式：

一个数，n

输出格式：

一个数，即答案不过，还得将答案与一个伟大的模数19491001膜一下

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

n≤10^8

略读题目，求1~n中互质的对数，便可想到欧拉函数。

如何计算欧拉函数

long long getphi(){

    int i=1;long long res=n;

    while(n>1){

        if(p[i]==0)break;

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

            res=(res/p[i])*(p[i]-1);

            while(n%p[i]==0)n/=p[i];

        }

        i++;

    }

    if(n>1)res=(res/n)*(n-1);

    return res;

}

除此之外，我们也可以通过欧拉函数的积性，使用线形欧拉打表：

 void get_phi(){

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

         if(!v[i]){

             prim[++id]=i;

             phi[i]=i-;

         }

         for(register int j=;j<=id;j++){

             if(i*prim[j]>n)break;

             v[i*prim[j]]=;

             if(i%prim[j]==){

                 phi[i*prim[j]]=(phi[i]*prim[j])%MOD;break;

             }

             else phi[i*prim[j]]=(phi[i]*(prim[j]-))%MOD;

         }

     }

 }

打完表后，循环就可以啦：

 #include <cstdio>

 #include <bitset>

 #include <iostream>

 using namespace std;

 const int MOD=;

 int n;

 bitset<> v;

 int prim[],id,phi[];

 void get_phi(){

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

         if(!v[i]){

             prim[++id]=i;

             phi[i]=i-;

         }

         for(register int j=;j<=id;j++){

             if(i*prim[j]>n)break;

             v[i*prim[j]]=;

             if(i%prim[j]==){

                 phi[i*prim[j]]=(phi[i]*prim[j])%MOD;break;

             }

             else phi[i*prim[j]]=(phi[i]*(prim[j]-))%MOD;

         }

     }

 }

 int main(){

     #ifndef ONLINE_JUDGE

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

     freopen("phi.out","w",stdout);

     #endif

     scanf("%d",&n);

     get_phi();long long ans=;

     for(int i=;i<=n;i++)ans=(ans+phi[i])%MOD;

     cout<<ans<<endl;

     return ;

 }

巴特西

T66099 小xzy的数对题解

T66099 小xzy的数对

题目背景

题目描述

我们认定11与任何数都互质。

输入输出格式

输入格式：

输出格式：

输入输出样例

说明

最新文章

热门文章

巴特西

T66099 小xzy的数对 题解

T66099 小xzy的数对

题目背景

题目描述

我们认定11与任何数都互质。

输入输出格式

输入格式：

输出格式：

输入输出样例

说明

最新文章

热门文章

T66099 小xzy的数对题解