2015年2月20日 星期五

2015/02/20 TIOJ 1615 . A! + B! problem

// http://tioj.ck.tp.edu.tw/problems/1615
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

bool is_prime[2000000];
vector<int> prime;

void set_prime()
{
    fill(is_prime, is_prime+2000000, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i*i < 2000000; i++)
    {
        if( !is_prime[i] ) continue;

        for(int j = i*i; j < 2000000; j += i)
            is_prime[j] = false;
    }

    prime.clear();

    for(int i = 2; i < 2000000; i++)
        if( is_prime[i] ) prime.push_back(i);
}

int A, B;

int main()
{
    set_prime();

    while( scanf("%d %d", &A, &B) != EOF )
    {
        if( A > B ) swap(A, B);

        int Ans = 0;

        for(int Ai = 1; Ai <= A; Ai++)
            if( is_prime[Ai] ) Ans++;

        ll num = 1;

        for(int Bi = A+1; Bi <= B; Bi++)
            num *= Bi;

        num++;

        for(int pi = 0; pi < prime.size(); pi++)
        {
            if( (ll)prime[pi]*prime[pi] > num ) break;

            if( num%prime[pi] == 0 )
            {
                if( prime[pi] > A ) Ans++;

                while( num%prime[pi] == 0 ) num /= prime[pi];
            }
        }

        if( num > A ) Ans++;

        printf("%d\n", Ans);
    }

}

沒有留言:

張貼留言