Input
第一行:CAS,代表数据组数(不大于350),以下CAS行,每行一个数字,保证在64位长整形范围内,并且没有负数。你需要对于每个数字:第一,检验是否是质数,是质数就输出Prime
第二,如果不是质数,输出它最大的质因子是哪个。
Output
第一行CAS(CAS<=350,代表测试数据的组数)
以下CAS行:每行一个数字,保证是在64位长整形范围内的正数。
对于每组测试数据:输出Prime,代表它是质数,或者输出它最大的质因子,代表它是和数
Sample Input
6
2
13
134
8897
1234567654321
1000000000000
2
13
134
8897
1234567654321
1000000000000
Sample Output
Prime
Prime
67
41
4649
5
Prime
67
41
4649
5
HINT
数据范围:
保证cas<=350,保证所有数字均在64位长整形范围内。
Solution
裸Pollard Rho题
但它不简单,反而很恶心
不知道为什么数据那么强
几个注意的:
1)乘法要写快速乘,原理是a%b=a-a/b*b
2)Miller Rabin最好优化
3)有些版本的Pollard Rho是错的。。。被坑了好久(数学一本通)
这东西本身有概率错误,导致调都不知道调哪里,最后是照着zhou888的代码一点一点边改边交边调的
#include<bits/stdc++.h> #define ll unsigned long long const int Count=5; int base[6]={0,2,3,5,7,61}; ll ans; template<typename T> inline void read(T &x) { T data=0,w=1; char ch=0; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar(); x=data*w; } template<typename T> inline void write(T x,char c='