作者bleed1979 (十三)
看板C_and_CPP
標題Re: [ACM ] 10139 WA
時間Sat Apr 18 14:19:18 2009
幫你改好了, 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
2F：→ AceKiller:可以fix這個bug 但還是WA orz... thx anyway 04/18 16:50
3F：推 AceKiller:bug fixed 04/18 21:05