http://acm.hdu.edu.cn/showproblem.php?pid=4135

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.

 

题目大意：求[a,b]区间与n互素的数的个数

思路：首先转化为前b个数满足的个数减去前a-1个数满足的个数

前num个数中与n互素的数的个数不好算，转化为num-前num个数中与n不互素（即除1外无公因数）的个数

将n分解为若干素数的乘积，求前num个数中有这些素数作为其因数的数的个数，比如前num个数中以3为因数的数有num/3个，

然后容斥定理，奇加偶减，枚举2^k中组合就行了，k为素数因数个数。

实现方式有三种，dfs枚举子集，队列数组，二进制枚举。

我新学了队列数组。

第一次出了小问题：第一次solve()把n给分解了，第二次n就不对了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll t,a,b,n;

ll solve(ll num,ll n)
{
	vector<int> prime,que;
	int m=sqrt(n+0.5);
	for(int i=2;i<=m;i++)if(n%i==0)
	{
		prime.push_back(i);
		while(n%i==0)n/=i;
	}
	if(n>1)prime.push_back(n);
	que.push_back(-1);
	for(int i=0;i<prime.size();i++)
	{
		int k=que.size();
		for(int j=0;j<k;j++)que.push_back(prime[i]*que[j]*-1);
	}
	ll ans=0;
	for(int i=1;i<que.size();i++)ans+=num/que[i];
	return num-ans;
}

int main()
{
//	freopen("input.in","r",stdin);
	int cnt=0;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>n;
		cout<<"Case #"<<++cnt<<": "<<solve(b,n)-solve(a-1,n)<<endl;
	}
	return 0;
}