首页 > 代码库 > HDOJ 5150 Sum Sum Sum Miller_Rabin
HDOJ 5150 Sum Sum Sum Miller_Rabin
很少有这么裸的题目,测一下Miller_Rabin
Sum Sum Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 72 Accepted Submission(s): 52
Problem Description
We call a positive number X P-number if there is not a positive number that is less than X and the greatest common divisor of these two numbers is bigger than 1.
Now you are given a sequence of integers. You task is to calculate the sum of P-numbers of the sequence.
Now you are given a sequence of integers. You task is to calculate the sum of P-numbers of the sequence.
Input
There are several test cases.
In each test case:
The first line contains a integerN(1≤N≤1000) . The second line contains N integers. Each integer is between 1 and 1000.
In each test case:
The first line contains a integer
Output
For each test case, output the sum of P-numbers of the sequence.
Sample Input
3 5 6 7 1 10
Sample Output
12 0
Source
BestCoder Round #24
/* *********************************************** Author :CKboss Created Time :2014年12月27日 星期六 21时51分17秒 File Name :HDOJ5150.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; /// Miller_Rabin typedef long long int LL; const int S=8;///判断几次 (8~12) /// (a*b)%c LL mult_mod(LL a,LL b,LL c) { a%=c; b%=c; LL ret=0; LL temp=a; while(b) { if(b&1) { ret+=temp; if(ret>c) ret-=c; } temp<<=1; if(temp>c) temp-=c; b>>=1LL; } return ret; } /// (a^n)%mod LL pow_mod(LL a,LL n,LL mod) { LL ret=1; LL temp=a%mod; while(n) { if(n&1) ret=mult_mod(ret,temp,mod); temp=mult_mod(temp,temp,mod); n>>=1LL; } return ret; } /// check a^(n-1)==1(mod n) bool check(LL a,LL n,LL x,LL t) { LL ret=pow_mod(a,x,n); LL 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(LL n) { if(n<2) return false; if(n==2) return true; if((n&1)==0) return false; LL x=n-1; LL t=0; while((x&1)==0) { x>>=1; t++;} srand(time(NULL)); for(int i=0;i<S;i++) { LL a=rand()%(n-1)+1; if(check(a,n,x,t)) return false; } return true; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while(scanf("%d",&n)!=EOF) { LL sum=0; LL x; for(int i=0;i<n;i++) { cin>>x; if(Miller_Rabin(x)||x==1) { sum+=x; } } cout<<sum<<endl; } return 0; }
HDOJ 5150 Sum Sum Sum Miller_Rabin
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。