hdu 4910 Problem about GCD
表示完全给跪了,打表找规律+大数值的素数检测。可参见这篇博客:HDU
4910 Problem about GCD(米勒拉宾)
Miller Rabin算法就是基于概率的素数测试算法,利用费马小定理,a^(p-1)%p = 1 {gcd(a,p) = 1 && prime(p)=true},随机多个小于p且大于0的a值,若均检测出p为素数,则可认为p是素数
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1000005;
typedef __int64 LL;
int vis[MAXN], nprm;
LL prim[MAXN];
void init_......
阅读全文