// 1652K 875MS G++ 1000
// 1648K 1313MS G++ 10000
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
const int MAX = 1000100;
char notPrime[MAX+1];
int PrimeNum;
int Primes[MAX];
void checkPrime() {
notPrime[0] = 1;
notPrime[1] = 1;
notPrime[2] = 0;
for (int i = 2; i <= (int)sqrt(MAX) + 1; i++) {
int k = 2;
while(k * i <= MAX) {
notPrime[k * i] = 1;
k++;
}
}
PrimeNum = 0;
for (int i = 2; i <= MAX; i++) {
if (!notPrime[i]) {
Primes[PrimeNum++] = i;
// printf("%d\n", i);
}
}
}
char BigNum[103];
int L;
int Kt[34];
void solve(char * bigNum, int L) {
int curLength = strlen(bigNum);
int KtLength = 0;
int units_length = 3;
while (curLength > 0) {
int curVal = 0;
if (curLength >= units_length) {
curVal = atoi(bigNum + curLength - units_length);
*(bigNum + curLength - units_length) = 0;
} else {
curVal = atoi(bigNum);
}
Kt[KtLength++] = curVal;
// printf("%d\n", curVal);
curLength -= units_length;
}
char good = 1;
int badNum = 0;
int Units_Val = pow(10, units_length);
for (int i = 0; Primes[i] < L; i++) {
int curPrime = Primes[i];
int reminder = 0;
for (int j = KtLength - 1; j >= 0; j--) {
long long curVal = (long long)Kt[j] + (long long)reminder * Units_Val;
reminder = curVal % curPrime;
if (j == 0) {
if (reminder == 0) {
good = 0;
badNum = curPrime;
}
}
}
if (!good) {
break;
}
}
if (good) {
printf("GOOD\n");
} else {
printf("BAD %d\n", badNum);
}
}
int main() {
checkPrime();
while(scanf("%s %d", BigNum, &L) != EOF) {
// printf("%s %d\n", BigNum, L);
if (BigNum[0] == '0' && L == 0) {
return 0;
}
solve(BigNum, L);
}
}
一道很好的数论题,学到了另外一种表示大数的方式: 大进制(一般都是千), 基本思路其实很朴素,首先对于输入的大数N 和 factorL,
用所有比L小的素数 对N进行整除测试,如果存在比L小的素数可以整除N的话,那么就是BAD, 并且输出此最小的素数,
因为题目给了L最多到1000000,因此,只要事先把所有比L小的素数都搞出来就足够题目中使用了,至于求法,直接用素数筛子即可,没啥技术含量。
然后就是判断某个素数K是否能整除N了,因为N是大数,因此不可能用基本类型来表示,而如果用传统的字符串法来表示N,那么判断整除将会非常麻烦,
这时候,就轮到大进制出场了,为了方便起见,用千进制(意思很好理解,就是基本的进制,只不过从10变成了1000),这样,用一个int数组就可以表示此大数了(N最多到10的100次方,因此可以预先分配足够的空间), 而如何判断整除,也要用到一些数学trick(直接除铁定不行,要一位一位的进行),
举个例子,对于十进制的数 5678, 判断其是否可以被3整除,可以采用这样的一位一位处理方法:
首先最高位 5 %3 = 2,
那么下一位: (3*10 + 6) % 3 = 0
继续: (0*10 + 7) % 3 = 1
继续: (1*10 + 8)%3 = 0
因为最后一次求余为0,因此5678可以被3整除。
这个trick其实很简单,就是小学级别的,算法概论也对求余这种运算很推崇,称其解决了一部分计算机大数的问题,因为很多时候,我们只关心余数,而不关心除数,因此,这时候,同余定理就很有用.
后来改成了万进制试了一把,发现速度反而降了,
还犯了基础问题,
long long curVal = Kt[j] + reminder * Units_Val;
在万进制时,后面两个会溢出(因为都是int型),不会因为赋值那边是long long就自动扩展的.
不过用char做同样操作,却没出错,因为