数学3（欧拉函数）

P13880 [蓝桥杯 2023 省 Java A] 互质数的个数

看完题面后很容易想到欧拉函数， 但是 $a^b$ 是一个很大的数， 考虑一些特殊的性质：$\phi \left(p^n\right)=(p-1)p^{n-1}$，（$p$ 为质数） 所以令 $a=\prod _{i=1}^n{p}_{i^{{\alpha }_i}}$， 所以 $a^b=\prod _{i=1}^n{p}_{i^{b{\alpha }_i}}$ 因为欧拉函数是积性函数， 所以 $\phi \left(a^b\right)=\prod _{i=1}^n\phi \left(p_{i^{b{\alpha }_i}}\right)=\prod _{i=1}^n(p_i-1)p_{i^{b{\alpha }_i-1}}$ 代码：

#include
using namespace std;
#define int unsigned long long
const int mod=998244353;
int a,b,ans=1;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}
signed main(){
	cin>>a>>b;
	int x=a;
	for(int i=2;i*i1) ans=(ans*(x-1)%mod*mi(x,b-1)%mod)%mod; 
	cout

`#include
using namespace std;
#define int unsigned long long
const int mod=998244353;
int a,b,ans=1;
int mi(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=mod;
        y/=2,x=x*x%mod;
    }
    return ans;
}
signed main(){
	cin>>a>>b;
	int x=a;
	for(int i=2;i*i
		int p=i,arf=0;
		while(x%i==0) x/=i,arf++;
		if(arf) ans=(ans*(p-1)%mod*mi(p,arf*b-1))%mod; 
	}
	if(x>1) ans=(ans*(x-1)%mod*mi(x,b-1)%mod)%mod; 
	cout
	return 0;
}`

P2568 GCD

$$\begin{array}{ll}& amp;\sum _{p\in prime}^n\sum _{i=1}^n\sum _{j=1}^n\left[\right(i,j)=p]\\ =& amp;\sum _{p\in prime}^n\sum _{i=1}^{\mathrm{\lfloor }n/p\mathrm{\rfloor }}\sum _{j=1}^{\mathrm{\lfloor }n/p\mathrm{\rfloor }}\left[\right(i,j)=1]\\ =& amp;\sum _{p\in prime}^n\left(2\sum _{i=1}^{\mathrm{\lfloor }n/p\mathrm{\rfloor }}\phi \right(i)-1{)}^{\text{[PARSE ERROR: Undefined("Circumflex")]}*\left(1\right)}\end{array}$$ 预处理欧拉函数的前缀和即可。

$\text{[PARSE ERROR: Undefined("Circumflex")]}*\left(1\right)$：由于 $(i,j)$ 与 $(j,i)$ 是等价的，所以只需要计算 $i$ 的因子，并把统计结果乘二即可。但是当且仅当 $i=j=p$ 会重复计算，所以减去一个一即可。

代码：

#include
using namespace std;
#define int long long
const int N=1e7+5;
int n,idx,ans;
int vis[N],prm[N],phi[N];
void euler(){
    phi[1]=1;
    for(int i=2;i>n;
    euler();
    for(int i=1;i

`#include
using namespace std;
#define int long long
const int N=1e7+5;
int n,idx,ans;
int vis[N],prm[N],phi[N];
void euler(){
    phi[1]=1;
    for(int i=2;i
        if(!vis[i]){
            prm[++idx]=i;
            phi[i]=i-1;
        }
        for(int j=1;1ll*i*prm[j]
            vis[i*prm[j]]=1;
            if(i%prm[j]==0){
                phi[i*prm[j]]=phi[i]*prm[j];
                break;
            }
			else phi[i*prm[j]]=phi[i]*(prm[j]-1);
        }
    }
}
signed main(){
    cin>>n;
    euler();
    for(int i=1;iphi[i]+=phi[i-1];
    for(int i=1;iphi[n/prm[i]]*2-1;
    cout
    return 0;
}`

P4388 付公主的矩形

如上图，我们把 $n$ 拆成了 $2*2$，也就是两个日字形，而对于每个日字形，满足周长的一半等于 $2+1$。

这样说可能比较抽象，我们再举一个例子：

如上图，我们把 $n$ 拆成了 $1*4$，而对于整个矩形，满足周长的一半等于 $4+1$。

也就是说，我们需要首先分解 $n$ 的因数，之后根据因数找到大矩形，且满足矩形周长的一半等于因数加一，但是这个显然只是一个特征，并不能用来得出答案。

但是当我们仔细分析以上两张图的区别，为什么第一张图的对角线会经过一个点？

原因在于大矩形的两边不互质，所以导致有一个等比缩小的矩形与其对角线斜率一致。

所以我们在分解完因数后，枚举小矩形边长，判断是否互质即可。

代码：

#include
using namespace std;
#define int long long
int n,ans;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
signed main(){
    cin>>n;
    for(int i=1;i*i

`#include
using namespace std;
#define int long long
int n,ans;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
signed main(){
    cin>>n;
    for(int i=1;i*i
    	if(n%i!=0) continue;
    	int x=i+1,y=n/i+1;
    	for(int j=1;2*j
    		int a=j,b=x-j;
    		if(gcd(a,b)==1) ans++;
    	}
    	if(x!=y) for(int j=1;2*j
    		int a=j,b=y-j;
    		if(gcd(a,b)==1) ans++;
    	}
    }
    cout
    return 0;
}`

P5091 【模板】扩展欧拉定理

欧拉定理：

当 $a,m\in Z$，且 $gcd(a,m)=1$ 时有： $a^{\mathrm{\phi }\left(m\right)}\equiv 1\left(modm\right)$。

所以 $a^b\equiv a^{bmod\mathrm{\phi }\left(m\right)}\left(modm\right)$。

扩展欧拉定理：

当 $a,m\in Z$ 时有： $$ a^b \equiv \begin{cases} a^b &b则有代码：

#include
using namespace std;
#define int long long

int a,m,p;

int phi(int n){
	int r=n;
	for(int i=2;i*i1) r=r/n*(n-1);
	return r;
}

int qp(int x,int y,int mod){
	int r=1;
	while(y){
		if(y&1) r=r*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return r;
}

signed main(){
	cin>>a>>m;
	p=phi(m);
	string s;
	cin>>s;
	bool f=0;
	int b=0;
	for(int i=0;i=p){
			f=1;
			b%=p;
		}
	}
	if(f) cout

`#include
using namespace std;
#define int long long

int a,m,p;

int phi(int n){
	int r=n;
	for(int i=2;i*i
		if(n%i==0){
			r=r/i*(i-1);
			while(n%i==0) n/=i;
		}
	}
	if(n>1) r=r/n*(n-1);
	return r;
}

int qp(int x,int y,int mod){
	int r=1;
	while(y){
		if(y&1) r=r*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return r;
}

signed main(){
	cin>>a>>m;
	p=phi(m);
	string s;
	cin>>s;
	bool f=0;
	int b=0;
	for(int i=0;is.size();i++){
		char c=s[i];
		b=b*10+(c-'0');
		if(b>=p){
			f=1;
			b%=p;
		}
	}
	if(f) coutqp(a,b+p,m);
	else coutqp(a,b,m);
	return 0;
}`