程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ2635 The Embarrassed Cryptographer 簡單數論

POJ2635 The Embarrassed Cryptographer 簡單數論

編輯:關於C++

 

看到這題的示意圖也是醉了~題意:給你一個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

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved