本文主要是介绍HDU 1395(欧拉定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
欧拉φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3 欧拉公式
那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互
素的正整数的个数，称为n的欧拉函数值，这里函数
φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
求欧拉函数的c语言函数:
int eular(int n) {
int ret=1,i;
for(i=2;i*i<=n;i++)
if(n%i==0)
{
n/=i,ret*=i-1;
while(n%i==0)
n/=i,ret*=i;
}
if(n>1)
ret*=n-1, cout << n << endl;
return ret;
}
求欧拉函数的c++程序：
#include <cstdio>
#include <cstdlib>
using namespace std;
#define N 10000000
int main(int argc, const char *argv[])
{
int *phi;
char *prime;
prime = (char*)malloc((N + 1) * sizeof(char));
prime[0] = prime[1] = 0;
for(int i = 2; i <= N; i++)
prime[i] = 1;
for(int i = 2; i * i <= N; i++)
if(prime[i])
for(int j = i * i; j <= N; j += i)
prime[j] = 0; //这段求出了N内的所有素数
phi = (int*)malloc((N + 1) * sizeof(int));
for(int i = 1; i <= N; i++)
phi[i] = i;
for(int i = 2; i <= N; i++)
if(prime[i])
for(int j = i; j <= N; j += i)
phi[j] = phi[j] / i * (i - 1); //此处注意先/i再*（i-1)，否则范围较大时会溢出
return 0;
} //这段求出了N内所有数的欧拉函数值
当a，n互质时，a^φ（n）=1（mod n）.
这道题目可以用暴力解决：
#include <cstdio>
void main()
{
int n, x, round;
while (scanf("%d", &n) != EOF)
{
if (n % 2 == 0 || n == 1)
{
printf("2^? mod %d = 1\n", n);
}
else
{
x = 1, round = 2;
while (round != 1)
{
round = round * 2 % n;
++x;
}
printf("2^%d mod %d = 1\n", x, n);
}
}
}
也可以用欧拉定理：
下面提供两个用欧拉定理解决的程序：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL __int64
LL t,e[1000];
LL mod;
LL euler_phi(LL n)//欧拉函数
{
LL m=sqrt(n+0.5);
LL ans=n,i;
for(i=2;i<=m;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)n=n/i;
}
}
if(n>1)ans=ans/n*(n-1);
return ans;
}
void find(LL n)
{
LL i;
e[t++]=n;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
if(i*i==n)
e[t++]=i;
else
{
e[t++]=i;
e[t++]=n/i;
}
}
}
}
LL pows(LL a,LL b)
{
LL s=1;
while(b)
{
if(b&1)
s=(s*a)%mod;
a=(a*a)%mod;
b=b>>1;
}
return s;
}
int main()
{
LL n;
while(cin>>n)
{
if(n%2==0||n==1)
cout<<"2^? mod "<<n<<" = 1"<<endl;
else
{
LL m,ans,i,s=2;
/*for(i=2;;i++)//直接暴力的方法
{
s=(s*2)%n;
if(s==1)
break;
}
ans=i;*/
m=euler_phi(n);
t=0;
find(m);
sort(e,e+t);
mod=n;
for(i=0;i<t;i++)
{
if(pows(2,e[i])==1)
{
ans=e[i];
break;
}
}
cout<<"2^"<<ans<<" mod "<<n<<" = 1"<<endl;
}
}
return 0;
}
/*
这题数据很水，可以直接暴力出来。
我要讲的使用定理求解这道题：
本题很容易发现n为偶数或者0时无解。所以2和n必定互质
欧拉定理:a^(euler_phi(n))≡1(mod n),(a,n互质)
其中euler_phi为欧拉函数，计算不超过n且与n互质的个数。求法是n*∏(pi-1)/pi,pi为n的质因子
m=euler_phi(n);
所以a^m%mod=1,不过m不一定是最小循环，但m是一个循环，则最小循环不定时m的一个因子，因而找出所有m的因子，暴力
搜索下就OK了
*/
/*做法要利用这样几个定理：
第一个是a^phi(m)%m=1
这个等式在m和a互质的时候一定成立
在这个题目中，因为a=2
所以m与a不互质，除非m为偶数
当然m=1的时候需要特殊处理下，这些都是小问题。
现在这个问题明了了，即在m为奇数(大于1)的时候一定有解。
那么就有人萌生了直接暴力的方法。当然对于这个题，直接暴力是可以的，我最先开始也是这样过的
但是今天重新做了一下这个题我仔细的思考了一下，发现果然有更加巧妙的方法来解决该类问题。
首先说暴力的缺点吧，大多数情况暴力其实还是非常快的，但是如果当m为一个非常大的质数，那么问题就严重了。因为质数的欧拉函数就是质数-1
那么也就是说，最坏情况下，我们可能要枚举很多次才能找到一个解
那么更为高效的方法是：把m的欧拉函数值，假设值为phi进行质因数分解
然后依次枚举phi的每一个因子，同时判断这个因子x是否满足2^x%m==1，不断更新一个最小值，最后得到答案。
那么为什么这样做就是对的呢？
首先需要知道：
a^x%m==1满足这个方程的最小x称为a对模m的指数。我们记做ordm(a)，如果ordm(a)==phi(m)则我们称a为模m的原根
有：a^X%m==1 <-===-> ordm(a)整除X
根据以上所说：a^phi(m)=1成立，那么phi(m)%ordm(a)==0也是成立的
所以ordm(a)就是phi的一个因子
所以分解phi然后枚举phi的因子的做法是正确的（恩，是有科学依据的。。哈哈）
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#define inf 99999999
#define maxn 1000000
using namespace std;
typedef __int64 ll;
bool flag[maxn];
ll prime[maxn];
void init()
{
ll i,j,num=0;
for(i=2;i<maxn;i++)
{
if(!flag[i])
{
prime[num++]=i;
for(j=i*i;j<maxn;j=j+i)
flag[j]=true;
}
}
}
ll eular(ll n)
{
ll i,res=1;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
res=res*(i-1);
n=n/i;
while(n%i==0)
{
res=res*i;
n=n/i;
}
}
if(n==1)
break;
}
if(n>1)
res=res*(n-1);
return res;
}
ll exmod(ll a,ll b,ll n)
{
ll ret=1;
for(;b;b>>=1,a=a*a%n)
if(b&1)
ret=ret*a%n;
return ret;
}
ll solve(ll n,ll fac[])
{
ll i,num=0;
for(i=0;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
n=n/prime[i];
fac[num++]=prime[i];
while(n%prime[i]==0)
{
n=n/prime[i];
fac[num++]=prime[i];
}
}
if(n==1)
break;
}
if(n>1)
fac[num++]=n;
return num;
}
void getans(ll n,ll mod)
{
ll fac[100],num,ans=n,i;
bool loop=true;
while(loop)
{
loop=false;
num=solve(n,fac);
for(i=0;i<num;i++)
{
if(exmod(2,n/fac[i],mod)==1)
{
loop=true;
if(n/fac[i]<ans)
ans=n/fac[i];
}
}
n=ans;
}
printf("2^%I64d mod %I64d = 1\n",ans,mod);
}
int main()
{
ll n,phi;
init();
while(scanf("%I64d",&n)!=EOF)
{
if(n%2==0||n==1)
{
printf("2^? mod %I64d = 1\n",n);
continue;
}
phi=eular(n);
getans(phi,n);
}
return 0;
}
这篇关于HDU 1395(欧拉定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
