POJ2635 The Embarrassed Cryptographer 簡單數論

POJ2635 The Embarrassed Cryptographer 簡單數論

看到這題的示意圖也是醉了~題意：給你一個k，他是兩個素數之積，然後給了一個數字L,然後找到具體是哪兩個素數相乘等於k,較小的那個素數是否小於L,若小於L就輸出 BAD外加較小的那個素數，否則就輸出“GOOD”，

剛拿到這題目，有些鑽牛角尖外加題意沒看清楚，一開始糾結於 K很大，若想具體找出兩個素數不可能，因為總有一個很大很大，求出其中一個素數 是否在10^6內是可以的，但是那時候我覺得還需要證明 k/prime 的值必須也是素數才符合要求，其實題目都規定好了 k必定是兩個素數之積 而不會由其它合數相乘構成，所以就簡單了許多

我不知道這個是什麼定理的，但是對於一個很長的數字 比如 123456789,若把它每位上數字存在數組num中，123456789%m也等於

int now = 0;

for(int i=0;i<9;i++) now = (now * 10 + num[i])%m;

如果知道這個的話就好做了，對於K其實可以轉化為大進制的數字存在數組裡，比如轉化為千進制萬進制，先保存好，最後 計算的時候再乘以一千或者一萬，上面那個for是相對於十進制的，把那個now*10改成對應進制即可，剩下的枚舉素數只需要打印素數表即可，一開始害怕K太大存不下來而沒有去細算直接轉化為萬進制，結果一直WA，後來轉化為千進制就過了，原因是 for循環時每次取余的時候，余數最大可達10^6,然後再乘10000就會爆int，然後又改成了 long long，轉化為萬進制，也是可以過的

string s;

int L;

int nnum[100000 + 5];

int cnt ;

bool isprime[1000000 + 55];
int prime[1000000 + 55];
int k;

void make_prime() {
	memset(isprime,false,sizeof(isprime));
	for(int i=2;i<1000055 ;i++)
		if(!isprime[i])
			for(int j=i*2;j<1000055;j+=i)
				isprime[j]=true;
	for(int i=2;i<1000055;i++)
		if(!isprime[i])
			prime[k++]=i;
}

void init() {
	memset(nnum,0,sizeof(nnum));
	cnt = 0;
}

bool input() {
	while(cin>>s>>L) {
		if(s == 0 && L == 0)break;
		return false;
	}
	return true;
}

void slove() {
	int len = s.length();
	for(int i=len - 1;i >= 0;i-=3) {
		for(int j= i - 2;j<=i;j++) {
			if(j < 0)j = 0;
			nnum[cnt] = nnum[cnt] * 10 + s[j] - '0';
		}
		cnt++;
	}
}

bool gao(int x) {
	int ret = 0;
	for(int i= cnt - 1;i>=0;i--) {
		ret = (ret * 1000 + nnum[i])%x;
	}
	if(ret)return false;
	return true;
}

void cal() {
	slove();
	for(int i=0;i