bzo4802 欧拉函数 miller_rabin pollard_rho

欧拉函数

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是到经典例题

主要用到了miller_rabin和pollard_rho,算法导论p567与p571文章地址https://www.yii666.com/article/756190.html网址:yii666.com

以下是比较理想代码,算法复杂度n^(1/4),及——根号根号n,用到了以下map文章来源地址https://www.yii666.com/article/756190.html

#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);
}
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

bzo4802 欧拉函数 miller_rabin pollard_rho-相关文章

  1. c语言总练习题

  2. BZOJ4805: 欧拉函数求和(杜教筛)

  3. BZOJ4802 欧拉函数 数论

  4. 【刷题】BZOJ 4805 欧拉函数求和

  5. BZOJ4802:欧拉函数(Pollard-Rho,欧拉函数)

  6. BZOJ 4802 欧拉函数

  7. bzo4802 欧拉函数 miller_rabin pollard_rho

  8. C++刷题——2830: 递归求1*1+2*2+3*3+……+n*n

      心得体会:这是一个简单递归函数,假设遇到复杂的递归函数。在写之前能够先找找规律,写成递归的形式。就比較好些了。继续努力。

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png