Phi的反函数
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
P4780 Phi的反函数
Phi(\(\varphi\) )定义
\(\varphi(n)\) 代表从1-n所有与n互质的数的个数
求\(\varphi(n)\)
普通求法:
首先将n唯一分解为
$n=x_1{p_1}*x_2{p_2}……*x_n^{p_n} $
\(\varphi(n)=n*(1-\frac1{x_1})*(1-\frac1{x_2})*……*(1-\frac1{x_n})\)
证明:
首先我们考虑在所有数中有\(\frac{1}{x}\)的概率会取到一个数是x的倍数,那么有\((1-\frac{1}{x})\)的概率会取到一个数不是x的倍数,1-n有n个数,我们要找到1-n所有与n互质的数,也就是去一个不是n的任意一个因数(x1,x2,x3……xn)的倍数,就得到以上式子
两个定理:
定理1证明:
1.在gcd(n,m)=1情况下
根据上述式子可以推导:
\(\varphi(nm)=n*m*(1-\frac1{x_1})……*(1-\frac1{x_n})*(1-\frac1{y_1})……*(1-\frac1{y_n})=\varphi(n)*\varphi(m)~~~~~~~~~~~~gcd(n,m)=m\)
2.在gcd(n,m)=m情况下
考虑感性理解,1-n里面有\(\varphi(n)\)个与n互质,那么扩大m倍,相当于有m个1-n就直接乘(因为我们保证了\(gcd(n,m)=m\)也就是n是m的倍数,所以不存在乘上m后多出了不属于n的因子)
定理2.\(\varphi(n)=n-1~~~~~~~~~~~~~n\in prim\)(这显而易见)
我们需要求Phi的反函数就要先深刻理解上述内容然后进行运用
可以根据上述定理1得到:
(在这里我们用到了定理一第一类和定理一第二类的一种特殊情况\(\varphi(n*n)=\varphi(n)*n\))
得出\(\varphi(x)=\varphi(a_1)*a_1^{p_1}*\varphi(a_2)*a_2^{p_2}*......\varphi(a_n)*a_n^{p_n}~~~~~~~~~~~~~~~~~~a_i\in prime\)
由定理二得:\(a_i\)都是质数,所以\(\varphi(a_i)=a_i-1\)
所有质数分解出来不超过10个,因为\(2*3*5*7*11*13*17*19*23*29=6469693230\)
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~2^{31}=2147483648\)
所以可以直接暴力搜索
(关于判断是否为质数的函数)
因为数据范围在2^{31} ,如果我们求2^{31} 范围内的质数,直接爆炸,
其实我们只需要找出2^{16}的质数,每次判断一下当前这个数now+1(也就是\(revphi(now)\))是不是质数
例如\(\varphi(x)=n=\varphi(3)*varphi(1e9+7)\)
第一次找到\(\varphi(3)\)处理以后,由于我们只找了2^{16}的质数,我们找不到\(\varphi(1e9+7)\)在里面,我们需要每次判断当前这是数是不是质数。
具体的:
第一次判断\(\varphi(3)*varphi(1e9+7)\)显然不是质数
除以\(\varphi(3)\)后变成了\(\varphi(1e9+7)\) 也就是now=1e9+6
第二次判断\((now+1)\in prime\) 那么直接把质数给除了,直接结束了AWA
那么怎么得出答案呢
\(\varphi(n)=\varphi(a_1)*a_1^{p_1}*\varphi(a_2)*a_2^{p_2}*......\varphi(a_n)*a_n^{p_n}~~~~~~~~~~~~~~~~~~a_i\in prime\)
我们再来重新看看这些式子
可以看出最后的\(ans=a_1*a_1^{p_1}*a_2*a_2^{p_2}*......*a_n*a_n^{p_n}\)
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+10;
int vis[N],s[30],tot=0,n,cnt=0;
ll ans=1e17+10,prim[N];
void shai(int x){
for(int i=2;i<=x;i++){
if(!vis[i]){
prim[++tot]=i;
}
for(int j=1;j<=tot&&i*prim[j]<=x;j++){
vis[prim[j]*i]=1;
if(!i%prim[j]){
break;
}
}
}
}//质数筛
bool is_p(ll x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
//cout<<x<<i<<endl;
return 0;
}
}
return 1;
}//判断是否为质数
void dfs(int now,int id,ll rev){//id代表当前干过的质数,是个优化
if(now>=ans) return ;//简单优化
if(now==1){
ans=min(rev,ans);
return ;
}
if(is_p(now+1)) dfs(1,id+1,rev*(now+1));
for(int i=id;i<=tot;i++){
if(now%(prim[i]-1)==0){
int a=now;
ll b=rev;
a/=(prim[i]-1);b*=prim[i]; //定理1的情况1
dfs(a,i+1,b);
while(a%prim[i]==0){//定理1的情况2
a/=prim[i];b*=prim[i];
dfs(a,i,b);
}
}
}
}
int main(){
scanf("%d",&n);
shai(sqrt(n)+1);
dfs(n,1,1);
if(ans==1e17+10){//无解或者太大了
printf("-1");
}else printf("%lld",ans);
return 0;
}
//2147483647
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |