ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1049. Brave Balloonists

WA 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?
Posted by Loky_Yuri [USTU] 12 Oct 2006 23:24
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?
Posted by dimozzz 1 Dec 2007 14:51
Number of divisor is 2470 :) .