很少有这么裸的题目,测一下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 thanX 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.
if there is not a positive number that is less than
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.
Input
There are several test cases.
In each test case:
The first line contains a integerN(1≤N≤1000) .
The second line containsN integers.
Each integer is between 1 and 1000.
In each test case:
The first line contains a integer
The second line contains
Each integer is between 1 and 1000.
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
/* ***********************************************
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;
}