首页 > 代码库 > POJ 2635 The Embarrassed Cryptographer 线性筛+高精度取模
POJ 2635 The Embarrassed Cryptographer 线性筛+高精度取模
题目大意:给两个数,第一个数的范文是10^100,第二个数10^6,第一个数是两个质数的乘积,问有没有不超过第二个数的数是第一个树的因子。
思路:10^6中只有7w+个素数,只要挨个判定能不能整除即可。然后这个题素数必须线性,不然就T。还有高精度一开始我压了4位,之后就wa,调了很长时间发现判断整除的过程中爆int了,换成long long就是T,最后十分生气,直接压到了7位,果断A了,好像时间还不慢。如果要用int的话,最多只能压3位,应该也能过。
CODE:
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1001000 using namespace std; struct BigInt{ int num[1010],len; BigInt(char *s) { memset(num,0,sizeof(num)); int length = strlen(s + 1); len = 0; for(int i = length; i > 0; i -= 7) { int p = 1; ++len; for(int j = 0; j <= 6 && i - j > 0; ++j) { num[len] += (s[i - j] - '0') * p; p *= 10; } } } bool Divide(int x) { long long remain = 0; for(int i = len; i; --i) remain = (remain * 10000000 + num[i]) % x; return !remain; } }; int prime[MAX],primes; bool notp[MAX]; char src[10010]; int L; void Pretreatment() { for(int i = 2; i < MAX; ++i) { if (!notp[i]) prime[++primes] = i; for(int j = 1; j <= primes && prime[j] * i < MAX; ++j) { notp[prime[j] * i] = 1; if (i % prime[j] == 0) break; } } } int main() { Pretreatment(); while(scanf("%s%d",src + 1,&L),L) { BigInt p(src); bool flag = false; for(int i = 1; i <= primes && prime[i] < L; ++i) if(p.Divide(prime[i])) { flag = true; printf("BAD %d\n",prime[i]); break; } if(!flag) puts("GOOD"); } return 0; }
POJ 2635 The Embarrassed Cryptographer 线性筛+高精度取模
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。