hdu 4135_Co-prime

/*  hdu 4135(反発原理)Hot~~招聘--亜信科技、巴卡斯(杭州)、壹晨仟陽(杭州)、英雄互娯楽(杭州)(2016級新入生を含む)校試合のほかに、ACM校チームに参加する方法はありますか?Co-prime Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3292    Accepted Submission(s): 1278 Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N. Two integers are said to be co-prime or relatively prime if they have no common positive divisors  other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively  prime to every integer.   Input The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=N <= 109).   Output For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.   Sample Input 2 1 10 2 3 15 5 Sample Output Case #1: 5 Case #2: 10
題意:(a,b)区間のn互質の数を求めさせる個数である.
Hint
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
using namespace std; 
__int64 s[1000],cou;
void find(__int64 n)
{
	__int64 i;
	cou = 0;
	for(i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			s[cou++] = i;
			while(n%i==0)
			{
				n /= i;
			}
		}
	}
	if(n>1)
	{
		s[cou++] = n;
	}
}
__int64 fun(__int64 x)
{
	__int64 q[10000],i,j,k,sum=0,t=0;
	q[t++] = -1;
	for(i=0;i<cou;i++)
	{
		k = t;
		for(j=0;j<k;j++)
		{
			q[t++] = s[i]*q[j]*(-1); 
		}
	}
	for(i=1;i<t;i++)
	{
		sum+=x/q[i]; 
	}	
	return sum;
}
int main()
{
	__int64 T,a,b,n,sum1,sum2,num=0;
	scanf("%I64d",&T);
	while(T--)
	{
		scanf("%I64d%I64d%I64d",&a,&b,&n);
		find(n);
		sum2 = b - fun(b);
		sum1 = (a-1)-fun(a-1);
		printf("Case #%I64d: %I64d
",++num,sum2-sum1);	
	}
	return 0;
}