手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

Phi的反函数

2023-01-15 19:02:06 来源：博客园

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.\begin{cases}\varphi(nm)=\varphi(n)*\varphi(m)~~~~~gcd(n,m)=1\\\varphi(nm)=\varphi(n)*m~~~~~~~~~~~gcd(n,m)=m\end{cases}\]

定理1证明：1.在gcd(n,m)=1情况下

根据上述式子可以推导：

\[n=x_1^{p_1}*x_2^{p_2}……*x_n^{p_n} \]\[m=y_1^{q_1}*y_2^{q_2}……*y_n^{q_n} \]\[n*m=x_1^{p_1}*x_2^{p_2}……*x_n^{p_n}*y_1^{q_1}*y_2^{q_2}……*y_n^{q_n} \]

$\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

那么怎么得出答案呢

\[1.\begin{cases}\varphi(nm)=\varphi(n)*\varphi(m)~~~~~gcd(n,m)=1\\\varphi(nm)=\varphi(n)*m~~~~~~~~~~~gcd(n,m)=m\end{cases}\]

$\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 #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<=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

关键词：我们需要因为我们