Re: [ACM ] 10139 WA

看板C_and_CPP (C/C++)作者bleed1979 (十三)時間16年前 (2009/04/18 14:19)推噓2(2推 0噓 1→)

留言3則, 1人參與討論串2/2 (看更多)

幫你改好了, m 不一定會被除盡, 這時就要判斷最後的 m 是否大於 n 大於就false, 小於等於就true 請參考94764610 284293833這個case 284293833 does not divide 94764610! #include<cstdio> #include<string> #include<cmath> using namespace std; # define P 46350 bool iscom[P]; unsigned int prime[5000]; int factor(unsigned int &test, unsigned int fac) { unsigned int count = 0; while(test % fac == 0) { test /= fac; count++; } return count; } int main() { unsigned int i, j, k, p, q, c, n, m, tmp; bool isprime, div; c = 0; for(i = 2; i <= P - 1; i++) { if(!iscom[i]) { prime[c] = i; c++; for(j = 2*i; j <= P - 1; j+=i) iscom[j] = true; } } while(scanf("%u %u", &n, &m) == 2) { tmp = m; if(m == 0 || (n == 0 && m != 1)) div = false; else if(n >= m || (n == 0 && m == 1)) div = true; else { isprime = true; for(i = 0; prime[i]*prime[i] <= m; i++) if(m % prime[i] == 0){ isprime = false; break; } if(isprime) div = false; else { div = true; for(i = 0; i < c; i++) { p = factor(m, prime[i]); if(p == 0) continue; q = 0; if(prime[i] <= n) { q = 1; for(j = 2*prime[i]; j <= n; j+=prime[i]) { k = j; q += factor(k, prime[i]); if(q >= p) break; } } if(q < p) { div = false; break; } if(m == 1) { div = true; break; } } if(m > 1 && m > n) { div = false; } } } if(div) printf("%u divides %u!\n", tmp, n); else printf("%u does not divide %u!\n", tmp, n); } return 0; } ※ 引述《AceKiller (皇牌殺手)》之銘言： : 這題我試過很多case都正確但是還是吃WA QQ : 下面是我的code 請強者們幫我看一下感激不盡 : #include<cstdio> : #include<string> : #include<cmath> : using namespace std; : # define P 46350 : bool iscom[P]; : unsigned int prime[5000]; : int factor(unsigned int &test, unsigned int fac) : { : unsigned int count = 0; : while(test % fac == 0) { : test /= fac; : count++; : } : return count; : } : int main() : { : unsigned int i, j, k, p, q, c, n, m, tmp; : bool isprime, div; : c = 0; : for(i = 2; i <= P; i++) { : if(!iscom[i]) { : prime[c] = i; : c++; : for(j = 2*i; j <= P; j+=i) : iscom[j] = true; : } : } : while(scanf("%u %u", &n, &m) == 2) { : tmp = m; : if(m == 0 || (n == 0 && m != 1)) : div = false; : else if(n >= m || (n == 0 && m == 1)) : div = true; : else { : isprime = true; : for(i = 0; prime[i]*prime[i] <= m; i++) : if(m % prime[i] == 0){ : isprime = false; : break; : } : if(isprime) div = false; : else { : div = true; : for(i = 0; i < c; i++) { : p = factor(m, prime[i]); : if(p == 0) : continue; : q = 1; : for(j = 2*prime[i]; j <= n; j+=prime[i]) { : k = j; : q += factor(k, prime[i]); : if(q >= p) : break; : } : if(q < p) { : div = false; : break; : } : if(m == 1) { : div = true; : break; : } : } : } : } : if(div) : printf("%u divides %u!\n", tmp, n); : else : printf("%u does not divide %u!\n", tmp, n); : } : return 0; : } -- World of bleed1979 http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.16.70