2015
04-16

# Co-prime

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.

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).

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).

2
1 10 2
3 15 5

Case #1: 5
Case #2: 10

HintIn the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.  

#include <cstdio>
int f[30],cnt;
typedef long long LL;
LL a,b;
int n;
LL tol,ans;
void dfs(int s,LL mul,int t)
{
if(s==cnt){
if(t) ans=ans+tol/mul;
else ans=ans-tol/mul;
return;
}
dfs(s+1,mul,t);
dfs(s+1,mul*f[s],1-t);
}
LL cal(LL x)
{
if(x==0) return 0;
tol=x;
ans=0;
dfs(0,1,1);
return ans;
}
int main()
{
// freopen("1.in","r",stdin);
int T,ca=0;
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d%d",&a,&b,&n);
if(n==1) { printf("Case #%d: %I64d\n",++ca,b-a+1);continue;}
cnt=0;
for(int j=2;j*j<=n;j++){
if(n%j==0){
f[cnt++]=j;
while(n%j==0) n/=j;
}
}
if(n>1) f[cnt++]=n;

// for(int i=0;i<cnt;i++) printf("%d\n",f[i]);
printf("Case #%d: %I64d\n",++ca,cal(b)-cal(a-1));
}
}

1. 我怎么感觉图1里那个小女孩打那个小男孩像好久以前一部视频里，小姑娘追打小男孩，一圈削到后脑勺上打趴下那个，几年过去了，终于发展成家庭战争了

2. 我怎么感觉图1里那个小女孩打那个小男孩像好久以前一部视频里，小姑娘追打小男孩，一圈削到后脑勺上打趴下那个，几年过去了，终于发展成家庭战争了

3. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

4. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的