欧拉函数学习笔记
读前警告：本文 MD 以及 \(\LaTeX\) 差到爆炸，因为是直接复制的。
首先，\(\varphi(n)\) 的值是 \(n\) 内与 \(n\) 互质的数的个数。
//求n的欧拉函数值： phi[n]
int getPhi(int n){
int ans = n;
for(int i = 2; i*i <= n; i++){
if(n % i == 0){
ans = ans * (i-1)/i;
while(n % i == 0) n /= i;
}
}
if(n > 1) ans = ans * (n-1)/n ;
return ans;
}
时间复杂度：sqrt(n)
你可能会问：你这玩意除了装X还有个【数据删除】用？
欸嘿还真不是，来了题你就知道了
T1
给定整数N和M，有多少整数X满足1<=X<=N且gcd（X，N）>=M？
第一行输入是一个整数T（T<=100），表示测试用例的数量。以下T行各包含两个数字N和M（2<=N<=100000000，1<=M<=N），表示一个测试用例。（注意这是个伏笔）
首先 \(N\) 最多有 \(\sqrt n\) 个因数（说实话大多数时间达不到这个上限）
设 \(d\) 是 \(N\) 的约数，且 \(d>=M\)。
其实它起的不是约数的作用，而是这个最大公因数！因为不管咋样 \(\gcd(N,X)\mid N\)。
枚举它，问题就成了 \(1\) 到 \(\frac{n}{d}\) 有多少数和 \(\frac{n}{d}\) 互质（\(\frac{n}{d}\) 即 \(X\)）。
欸这好像是 \(\varphi(\frac{n}{d})\) 欸！
然后就水了，直接求和。
对了记得伏笔吗？这个 \(\varphi\) 不能线性筛求，得用它自己的计算公式。
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
LL phi(LL n)
{
LL sum=n;
for(LL i=2;i*i<=n;i++)
{
if(n%i==0)
{
sum=sum*(i-1)/i;
while(n%i==0)n/=i;
}
}
if(n>1)sum=sum*(n-1)/n;
return sum;
}
LL t,n,m,p[100010],o;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
LL sum=0;
o=0;
for(LL i=1;i*i<n;i++)
{
if(n%i==0)
{
p[++o]=i;
p[++o]=n/i;
}
}
LL s=sqrt(n);
if(s*s==n)p[++o]=s;
rep(i,1,o,1)
{
if(p[i]>=m)sum+=phi(n/p[i]);
}
cout<<sum<<endl;
}
return 0;
}
T2
给定一个正整数N，你的任务是计算小于N且和N不互质的正整数的和。如果A，B除了1之外没有公共的正约数，则称A与B互质。
考虑补集，求出所有互质的数的总和。
利用欧拉函数和欧几里德定理，可知若 \(\gcd(n,i)=1\) 则 \(\gcd(n,n-i)=1\)。
于是乎所有与 \(n\) 互质的数的和为 \(\frac{n\times \varphi(n)}{2}\)（和为 \(n\)，有 \(\frac{\varphi(n)}{2}\) 对）
那不互质的就是 \(\frac{n\times (n-1)-n\times \varphi(n)}{2}\)。
#include<stdio.h>
#include<bits/stdc++.h>
#define MOD 1000000007
#define LL long long
using namespace std;
LL phi(LL n)
{
LL sum=n;
for(LL i=2;i*i<=n;i++)
{
if(n%i==0)
{
sum=sum*(i-1)/i;
sum%=MOD;
while(n%i==0)n/=i;
}
}
if(n>1)sum=sum*(n-1)/n;
sum%=MOD;
return sum;
}
LL n;
int main()
{
cin>>n;
while(n!=0)
{
cout<<(n*(n-1)/2%MOD-phi(n)*n/2%MOD+MOD)%MOD<<endl;
cin>>n;
}
return 0;
}
T3
洛谷P2303
暴力硬拆！！！！
爆枚 \(n\) 因数！！！
爆算 \(\varphi(\frac{n}{d})\)！！！！
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
LL phi(LL n)
{
LL sum=n;
for(LL i=2;i*i<=n;i++)
{
if(n%i==0)
{
sum=sum*(i-1)/i;
while(n%i==0)n/=i;
}
}
if(n>1)sum=sum*(n-1)/n;
return sum;
}
LL t,n;
int main()
{
cin>>n;
LL sum=0;
for(LL i=1;i*i<=n;i++)
{
if(n%i==0)
{
sum+=i*phi(n/i);
if(i*i!=n)sum+=(n/i)*phi(i);
}
}
cout<<sum<<endl;
return 0;
}