|
|
back to boardWA on Test 3. What's wrong? Posted by whutes 12 Oct 2006 13:30 I think the algorithm is pretty straightforward. First calculate all the primes between 1 and 10000, then for each of the 10 number, records the number of different primes which are divisors of the number. Then use the formula (num1+1)*(num2+1)*...*(numN+1) where numi is the number of occurences of the ith prime in [1, 10000]. My code: =========================================================== #include <iostream> #include <cstdlib> #include <vector> using namespace std; int main() { vector<int> primes; bool e[10001]; for(int i = 2; i <= 10000; i++) e[i] = true; for(int i = 2; i <= 10000; i++) if(e[i]) for(int j = 2; j <= 10000/i; j++) e[j*i] = false; for(int i = 2; i <= 10000; i++) if(e[i]) primes.push_back(i);
int num[10001]; for(int i = 0; i < primes.size(); i++) num[i] = 0; for(int i = 0; i < 10; i++) { int n; cin >> n; for(int j = 0; j < primes.size(); j++) if(!(n%primes[j])) num[j]++; } int total = 1; for(int i = 0; i < primes.size(); i++) total = total*(num[i]+1)%10; cout << (total%10) << endl; //system("PAUSE"); return 0; } Re: WA on Test 3. What's wrong? I didn't look through your solution, but I can give you test, at which your program give wrong answer: 10 20 30 40 50 60 70 80 90 100 wright answer is 0 and your's is 8 ( (because number of divisors is 2340) Re: WA on Test 3. What's wrong? Posted by whutes 13 Oct 2006 02:15 Thank you very much. I got AC. Re: WA on Test 3. What's wrong? Number of divisor is 2470 :) . |
|
|