容斥原理是在計數時，必須注意沒有重複，沒有遺漏。于是人們想出來的一種計數方法：先不考慮重疊的情況，把包含于某内容中的所有對象的數目先計算出來，然後再把計數時重複計算的數目排斥出去，使得計算的結果既無遺漏又無重複。用兩個集合來講就是A∪B =|A∪B| = |A|+|B| - |A∩B |，如果是三個集合的話就是|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|，不難發現，出現的元素是奇數就加，偶數就減，這個原理應該也比較好懂，n個元素就總共有2^n-1種取法，隻要把這2^n-1種東西列出來，奇加偶減就可以解決。
容斥原理在計算互質的數的個數的時候應用的比較廣泛，因為一個數可以分解成幾個質因子，和它互質的數就是不擁有相同質因子的數，是以我們在某個區間中用容斥原理找到與它不互質的數的個數，再用全集去減即可得到答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll prime[70];
ll m,n;
void get_prime()
{
for(ll i=2;i*i<=n;i++)
if(n&&n%i==0) //對n進行素因數分解
{
prime[m++]=i;
while(n&&n%i==0) n/=i;
}
if(n>1) prime[m++]=n;
}
ll solve(ll num)
{
ll i,j;
ll ans=0,tem,flag;
for(i=1;i<1<<m;i++)
{
tem=1,flag=0;
for(j=0;j<m;j++)
if(i&1<<j)
flag++,tem*=prime[j];
if(flag&1) ans += num/tem; //容斥原理，奇加偶減
else ans -= num/tem;
}
return ans;
}
int main()
{
int t;
ll a,b,k=1;
scanf("%d",&t);
while(t--)
{
m=0;
scanf("%lld%lld%lld",&a,&b,&n);
get_prime();
printf("%lld\n",b-solve(b)-(a-1-solve(a-1)));
}
return 0;
}