首页 > > 程序设计 > C/C++ >

bzo4802 欧拉函数 miller_rabin pollard_rho

2018-06-17 22:46:24来源：未知阅读 ()

欧拉函数

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

Sample Output

HINT

Source

By FancyCoder

大整数分解主要背代码，证明非常麻烦。

题目bzoj4802是到经典例题

主要用到了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=50;
int number=0;
map<ll,int>m;
ll q_mul(ll a,ll b,ll mod)
{
    ll ans=0;
    while (b)
    {
        if (b&1)
        {
            ans=(ans+a)%mod;
        }
        b/=2;
        a=(a+a)%mod;
    }
    return ans;
}
ll q_pow(ll a,ll b,ll mod)
{
    ll ans=1;
    while (b)
    {
        if (b&1)
        {
            ans=q_mul(ans,a,mod);
        }
        b/=2;
        a=q_mul(a,a,mod);
    }
    return ans;
}
bool witness(ll a,ll n)
{
    ll tem=n-1;
    int j=0;
    while (tem%2==0)
    {
        tem/=2;
        j++;
    }
    ll p;
    ll x=q_pow(a,tem,n);
    while (j--)
    {
        p=q_mul(x,x,n);
        if (p==1 && x!=1 && x!=n-1) return true;
        x=p;
    } 
    if (p!=1) return true;
    else return false;
}
bool miller_rabin(ll n)
{
    if (n==2)
        return true;
    if (n<2||n%2==0)
        return false;
    for (int i=1;i<=times;i++)
    {
        long long a=rand()%(n-1)+1;
        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=1,k=2;
    x=rand()%(n);
    y=x;
    while(1)
    {
        i++;
        x=(q_mul(x,x,n)+c)%n;
        d=gcd(y-x,n);
        if (1<d&&d<n)
            return d;
        if (y==x)
            return n;
        if (i==k)
        {
            y=x;
            k*=2;    
        }        
        if (i*i>n) return n;
    }
}
void find(ll n)
{
    if (n==1) 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=0;
        m.clear();
        find(tar);
        for (map<ll,int>::iterator c=m.begin();c!=m.end();++c)
        {
            ll x=c->first;
            fzy=fzy/x*(x-1);
        }
        printf("%lld\n",fzy);
    }
}