大佬教程收集整理的这篇文章主要介绍了hdu3864,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
//============================================================================ // Name : HDU3864.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++,Ansi-style //============================================================================ #include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <time.h> using namespace std; const int S=2; long long mult_mod(long long a,long long b,long long c) { a%=c; b%=c; long long ret=0; while(b) { if(b&1){ret+=a;ret%=c;} a<<=1; if(a>=c)a%=c; b>>=1; } return ret; } long long pow_mod(long long x,long long n,long long mod) { if(n==1)return x%mod; x%=mod; long long tmp=x; long long ret=1; while(n) { if(n&1)ret=mult_mod(ret,tmp,mod); tmp=mult_mod(tmp,mod); n>>=1; } return ret; } long long check(long long a,long long x,long long t) { long long ret=pow_mod(a,x,n); long long last=ret; for(int i=1;i<=t;i++) { ret=mult_mod(ret,ret,n); if(ret==1 && last!=1 &&last!=n-1)return true; last=ret; } if(ret!=1)return true; return false; } bool Miller_Rabin(long long n) { if(n<2)return false; if(n==2)return true; if((n&1)==0)return false; long long x=n-1; long long t=0; while((x&1)==0){x>>=1;t++;} for(int i=0;i<S;i++) { long long a=rand()%(n-1)+1; if(check(a,n,t)) return false; } return true; } long long factor[100]; int tol; long long gcd(long long a,long long b) { if(a==0)return 1; if(a<0)return gcd(-a,b); while(b) { long long t=a%b; a=b; b=t; } return a; } long long Pollard_rho(long long x,long long c) { long long i=1,k=2; long long x0=rand()%x; long long y=x0; while(1) { i++; x0=(mult_mod(x0,x0,x)+c)%x; long long d=gcd(y-x0,x); if(d!=1&&d!=x)return d; if(y==x0)return x; if(i==k) { y=x0; k+=k; } } } void findfac(long long n) { if(Miller_Rabin(n)) { factor[tol++]=n; return; } long long p=n; while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } int main() { srand(time(NULL)); long long n; while(scanf("%I64d",&n)==1) { if(n==1) { printf("is not a D_num\n"); continue; } tol=0; findfac(n); if(tol!=2 && tol!=3) { printf("is not a D_num\n"); continue; } sort(factor,factor+tol); if(tol==2) { if(factor[0]!=factor[1]) { printf("%I64d %I64d %I64d\n",factor[0],factor[1],factor[0]*factor[1]); continue; } else { printf("is not a D_num\n"); continue; } } if(tol==3) { if(factor[0]==factor[1]&&factor[1]==factor[2]) { printf("%I64d %I64d %I64d\n",factor[0]*factor[1],factor[0]*factor[1]*factor[2]); continue; } else { printf("is not a D_num\n"); continue; } } } return 0; }
以上是大佬教程为你收集整理的hdu3864全部内容,希望文章能够帮你解决hdu3864所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。