[數學]1615 - A! + B! problem

Shaymin

原題：http://tioj.ck.tp.edu.tw/problems/1615
AC：http://tioj.ck.tp.edu.tw/submissions/9034

[tex]A%21+B%21%3DA%21%281+%28A+1%29%28A+2%29......B%29[/tex]，[tex]A![/tex]的質因數就是小於[tex]A[/tex]的質數個數，重點在後面那一大坨東西有多少質因數。此時根據題目的另一個條件[tex]max%28A%21%2C%20B%21%29%20/%20min%28A%21%2C%20B%21%29%20%5Cleq%201000000000000[/tex]，發現該數開根號為[tex]10^6[/tex]，於是枚舉所有小於根號那陀的質數來除，最後判斷那陀是不是質數就差不多了

[C++] 純文本查看 復制代碼

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;
#define MAX 1000001
bool isnp[MAX]={true,true,false};
int dp[MAX]={0};
vector<int> prime;
int main()
{
	int A=2,B,ans;
	while(A<1001)
	{
		if(!isnp[A])
		{
			B=A*A;
			while(B<MAX)
			{
				isnp[B]=true;
				B+=A;
			}
		}
		++A;
	}
	for(int i=1;i<MAX;++i)
	{
		dp[i] = dp[i-1];;
		if(!isnp[i])
		{
			dp[i]++;
			prime.push_back(i);
		}
	}
	/*
	A! = 1*2*3*..*A
	B! = 1*2*3*..*A*...B
	A!+B! = A!(1+(A+1)*(A+2)*...B)
	(1+(A+1)*(A+2)*...B) is prime? 
	*/
	while(cin>>A>>B)
	{
		if(A>B)swap(A,B);
		ans=dp[A];
		ll left = 1;
		for(ll i=A+1;i<=B;++i)
			left=left*i;
		++left;
		for(int i=0; i<prime.size() && prime[i]<=A ;++i)
		{
			while( left % prime[i] ==0 )left/=prime[i];
		}
		for(int c:prime)
		{
			if( left%c ==0 )
			{
				ans++;
				while( left%c ==0 )left/=c;
			}
		}
		if(left>1)ans++;
		cout<<ans<<'\n';
	}
}