欧拉函数
Time Limit: 5 Sec Memory Limit: 256 MB
Submit: 1112 Solved: 418
[Submit][Status][Discuss]
Description
已知N，求phi(N)
Input
正整数N。N<=10^18
Output
输出phi(N)
Sample Input
8
Sample Output
4
HINT
Source
By FancyCoder网址:yii666.com文章来源地址:https://www.yii666.com/article/756190.html
大整数分解主要背代码，证明非常麻烦。
题目bzoj4802是到经典例题文章地址https://www.yii666.com/article/756190.html
主要用到了miller_rabin和pollard_rho，算法导论p567与p571
以下是比较理想代码，算法复杂度n^(1/4),及——根号根号n，用到了以下map
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
#include<ctime>
typedef long long ll;
using namespace std;
const int times=;
int number=;
map<ll,int>m;
ll q_mul(ll a,ll b,ll mod)
{
ll ans=;
while (b)
{
if (b&)
{
ans=(ans+a)%mod;
}
b/=;
a=(a+a)%mod;
}
return ans;
}
ll q_pow(ll a,ll b,ll mod)
{
ll ans=;
while (b)
{
if (b&)
{
ans=q_mul(ans,a,mod);
}
b/=;
a=q_mul(a,a,mod);
}
return ans;
}
bool witness(ll a,ll n)
{
ll tem=n-;
int j=;
while (tem%==)
{
tem/=;
j++;
}
ll p;
ll x=q_pow(a,tem,n);
while (j--)
{
p=q_mul(x,x,n);
if (p== && x!= && x!=n-) return true;
x=p;
}
if (p!=) return true;
else return false;
}
bool miller_rabin(ll n)
{
if (n==)
return true;
if (n<||n%==)
return false;
for (int i=;i<=times;i++)
{
long long a=rand()%(n-)+;
if (witness(a,n))
return false;
}
return true;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
long long pollard_rho(ll n,ll c)
{
ll x,y,d,i=,k=;
x=rand()%(n);
y=x;
while()
{
i++;
x=(q_mul(x,x,n)+c)%n;
d=gcd(y-x,n);
if (<d&&d<n)
return d;
if (y==x)
return n;
if (i==k)
{
y=x;
k*=;
}
if (i*i>n) return n;
}
}
void find(ll n)
{
if (n==) return;
if(miller_rabin(n))
{
m[n]++;
number++;
return;
}
ll p=n;
while (p==n)
p=pollard_rho(p,rand()%(n));
find(p);
find(n/p);
}
int main()
{
srand((unsigned)time(NULL));
ll tar;
while (~scanf("%lld",&tar))
{
ll fzy=tar;
number=;
m.clear();
find(tar);
for (map<ll,int>::iterator c=m.begin();c!=m.end();++c)
{
ll x=c->first;
fzy=fzy/x*(x-);
}
printf("%lld\n",fzy);
}
}