T66099 小xzy的数对题解

T66099 小xzy的数对

题目背景

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

题目描述

学生发生冲突当且仅当他们身上的编号有大于

我们认定

输入输出格式

输入格式：

一个数，

输出格式：

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

输入输出样例

输入样例#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;
}

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

 1 void get_phi(){
 2     for(register int i=2;i<=n;i++){
 3         if(!v[i]){
 4             prim[++id]=i;
 5             phi[i]=i-1;
 6         }
 7         for(register int j=1;j<=id;j++){
 8             if(i*prim[j]>n)break;
 9             v[i*prim[j]]=0;
10             if(i%prim[j]==0){
11                 phi[i*prim[j]]=(phi[i]*prim[j])%MOD;break;
12             }
13             else phi[i*prim[j]]=(phi[i]*(prim[j]-1))%MOD;
14         }
15     }
16 }

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

 1 #include <cstdio>
 2 #include <bitset>
 3 #include <iostream>
 4 using namespace std;
 5 const int MOD=19491001;
 6 int n;
 7 bitset<100000000> v;
 8 int prim[100000000],id,phi[100000050];
 9 
10 void get_phi(){
11     for(register int i=2;i<=n;i++){
12         if(!v[i]){
13             prim[++id]=i;
14             phi[i]=i-1;
15         }
16         for(register int j=1;j<=id;j++){
17             if(i*prim[j]>n)break;
18             v[i*prim[j]]=1;
19             if(i%prim[j]==0){
20                 phi[i*prim[j]]=(phi[i]*prim[j])%MOD;break;
21             }
22             else phi[i*prim[j]]=(phi[i]*(prim[j]-1))%MOD;
23         }
24     }
25 }
26 
27 int main(){
28     #ifndef ONLINE_JUDGE
29     freopen("phi.in","r",stdin);
30     freopen("phi.out","w",stdout);
31     #endif
32     scanf("%d",&n);
33     get_phi();long long ans=0;
34     for(int i=1;i<=n;i++)ans=(ans+phi[i])%MOD;
35     cout<<ans<<endl;
36     return 0;
37 }

T66099 小xzy的数对 题解