BZOJ4802 欧拉函数 数论

原文链接http://www.cnblogs.com/zhouzhendong/p/8117744.html


题目传送门 - BZOJ4802


题意概括

Description

已知N,求phi(N)

Input网址:yii666.com<

正整数N。N<=10^18

题解

  Miller_Rabin+Pollard_Rho文章来源地址https://www.yii666.com/article/756194.html

  至于Pollard_Rho,我感到很奇怪。判定的时候为何不能丢第一个值!!

  请看下面两个代码,第一个对的,第二个错的……

BZOJ4802 欧拉函数 数论网址:yii666.com文章来源地址:https://www.yii666.com/article/756194.html


代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){
return b?gcd(b,a%b):a;
}
LL Mul(LL a,LL b,LL mod){
LL ans=0;
a%=mod;
while (b){
if (b&1)
ans=(ans+a)%mod;
b>>=1,a=(a<<1)%mod;
}
return ans;
}
LL Pow(LL a,LL b,LL mod){
LL ans=1;
a%=mod;
while (b){
if (b&1)
ans=Mul(ans,a,mod);
b>>=1,a=Mul(a,a,mod);
}
return ans;
}
bool Miller_Rabin(LL n){
if (n==2)
return 1;
if (n<2||n%2==0)
return 0;
LL m=n-1,k=0;
while (!(m&1))
m>>=1,k++;
for (int i=0;i<10;i++){
LL a=rand()%(n-1)+1,x=Pow(a,m,n),y;
for (int j=0;j<k;j++){
y=Mul(x,x,n);
if (y==1&&x!=1&&x!=n-1)
return 0;
x=y;
}
if (x!=1)
return 0;
}
return 1;
}
LL rnd(LL x,LL n,LL c){
return (Mul(x,x,n)+c)%n;
}
LL Pollard_Rho(LL n,LL c){
LL x,y;
while (1){
x=rand()%(n-1)+1,y=rnd(x,n,c);
while (1){
if (x==y)
break;
LL d=gcd(llabs(y-x)%n,n);
if (1<d&&d<n)
return d;
x=rnd(x,n,c);
y=rnd(rnd(y,n,c),n,c);
}
c=rand()%n;
}
}
LL n,x[66],pcnt;
void find(LL n){
if (n==1)
return;
if (Miller_Rabin(n)){
x[++pcnt]=n;
return;
}
LL p=Pollard_Rho(n,rand()%n);
find(p);
find(n/p);
}
int main(){
srand(19260817);
scanf("%lld",&n);
pcnt=0;
find(n);
sort(x+1,x+pcnt+1);
LL yz=pcnt?x[1]-1:1;
for (int i=2;i<=pcnt;i++)
yz=yz*(x[i]-(bool)(x[i]!=x[i-1]));
printf("%lld\n",yz);
return 0;
}

  文章地址https://www.yii666.com/article/756194.html

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

BZOJ4802 欧拉函数 数论-相关文章

  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