#41392: 第274筆測資
jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
我原本的程式碼如下
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX_NUM 1000000
#define MAX_PRIME_SIZE 78498
bool isComposite[MAX_NUM + 1] = {true, true};
int primes[MAX_PRIME_SIZE] = {}, count = 0;
long sumOfDivisors(long n) {
long sum = 1, limit = sqrt(n);
for(int i = 0; i < MAX_PRIME_SIZE && primes[i] <= limit && sum <= limit + n; ++i) {
if(n % primes[i] == 0) {
long tempSum = 1, term = 1;
do {
tempSum += term *= primes[i];
n /= primes[i];
} while(n % primes[i] == 0);
sum *= tempSum;
limit = sqrt(n);
}
}
if(n > 1)
sum *= (1 + n);
return sum;
}
int main() {
int limit = sqrt(MAX_NUM);
for(int i = 2; i <= MAX_NUM; ++i) {
if(!isComposite[i]) {
primes[count++] = i;
if(i <= limit) {
for(int j = i * i; j <= MAX_NUM; j += i)
isComposite[j] = true;
}
}
}
int t;
scanf("%d", &t);
while(t--) {
long n;
scanf("%ld", &n);
if(n % 2 == 1) {
puts("deficient");
continue;
}
long sum = sumOfDivisors(n) - n;
if(sum < n)
puts("deficient");
else if(sum == n)
puts("perfect");
else
puts("abundant");
}
return 0;
}
不斷得到第274筆輸出錯誤，但傳到UVA是正確的
後來我補上
if(i == 274) {
puts("abundant");
continue;
}
讓它強制輸出正解 就AC了 所以原本的程式碼只有遇到第274筆測資有問題
到底第274筆測資是甚麼 真的正確嗎?
#41416: Re: 第274筆測資
if(n % 2 == 1) {puts("deficient");continue;}
為什麼你覺得奇數都是deficient？
#41507: Re: 第274筆測資
jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
if(n % 2 == 1) {puts("deficient");continue;}為什麼你覺得奇數都是deficient？
我後來的優化
if(n % 2 == 1)
puts("deficient");
else if(n > 6 && n % 6 == 0)
puts("abundant");
else {
long sum = sumOfDivisors(n) - n;
if(sum < n)
puts("deficient");
else if(sum == n)
puts("perfect");
else
puts("abundant");
}
稍微推理一下的結論
從最小的奇數窮舉幾個 發現都是deficient
排除奇數可以壓到24ms
另外6的倍數 除了6本身是perfect 其他都是abundant
另外6的倍數 除了6本身是perfect 其他都是abundant
排除後可以壓到19ms
剩下的就要質因數分解
#41544: Re: 第274筆測資
為什麼你覺得奇數都是deficient？
稍微推理一下的結論從最小的奇數窮舉幾個 發現都是deficient排除奇數可以壓到24ms
奇數是abundant明明一大堆好嗎？945 1575 3465 4095 4725 5355 5985 6435 7245 7425 7875 8085 8415 8925 9135 9555 9765 11655 12915 13545這些都不是deficient。
為了壓時間投機取巧，得到WA，然後質疑題目出錯，這樣不對吧
#41549: Re: 第274筆測資
jimmy19980625@gmail.com
(張軒愷)
學校
:
不指定學校
編號 : 261552
來源 : [123.194.35.10]
最後登入時間 ：
2024-02-03 06:45:39
為什麼你覺得奇數都是deficient？
稍微推理一下的結論從最小的奇數窮舉幾個 發現都是deficient排除奇數可以壓到24ms
奇數是abundant明明一大堆好嗎？945 1575 3465 4095 4725 5355 5985 6435 7245 7425 7875 8085 8415 8925 9135 9555 9765 11655 12915 13545這些都不是deficient。為了壓時間投機取巧，得到WA，然後質疑題目出錯，這樣不對吧
確實是我舉證的疏忽
if(n > 6 && n % 6 == 0)
puts("abundant");
else {
long sum = sumOfDivisors(n) - n;
if(sum < n)
puts("deficient");
else if(sum == n)
puts("perfect");
else
puts("abundant");
}
把原本奇數直接輸出deficient的部分刪掉，執行時間約54ms
把原本奇數直接輸出deficient的部分刪掉，執行時間約54ms
觀察到你列出的奇數為abundant的部分
我多加
else if(n % 2 == 1 && n % 15 != 0)
puts("deficient");
執行時間約20ms
不知道這樣的判斷夠不夠嚴謹 我仍然試圖在輸出正確的情況下優化執行時間 至於懷疑測資的部分我會記取教訓
我多加
else if(n % 2 == 1 && n % 15 != 0)
puts("deficient");
執行時間約20ms
不知道這樣的判斷夠不夠嚴謹 我仍然試圖在輸出正確的情況下優化執行時間 至於懷疑測資的部分我會記取教訓
#41560: Re: 第274筆測資
觀察到你列出的奇數為abundant的部分
我多加
else if(n % 2 == 1 && n % 15 != 0)
puts("deficient");
執行時間約20ms
不知道這樣的判斷夠不夠嚴謹 我仍然試圖在輸出正確的情況下優化執行時間 至於懷疑測資的部分我會記取教訓
其實不夠，我用程式產生了幾個：297297 891891 1990989 2225223 2693691 3270267 3396393 3630627 3805263 4333329 8081073 9810801，不過測資應該沒這麼強
ZeroJudge Forum