介绍
Co-prime HDU - 4135
用位运算生成所有可能

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=1e3+5;
ll a,b,n;
int num;
ll fac[N];
void factor()
{
    ll tn=n;
    num=0;
    for(ll i=2;i*i<=n;i++)
    {
        if(tn%i==0)
        {
            fac[num++]=i;
            while(tn%i==0)
                tn/=i;
        }
    }
    if(tn>1)
        fac[num++]=tn;
}
ll solve(ll x)
{
    ll ans=0;
    for(int i=1;i<(1<<num);i++)//(1)
    {
        ll res=1;
        int cnt=0;
        for(int j=0;j<num;j++)//遍历n所有的素因子
        {
            if(i&(1<<j))//(2)
            {
                cnt++;
                res*=fac[j];
            }
        }
        if(cnt&1)
            ans+=(x/res);
        else
            ans-=(x/res);
    }
    return ans;
}
int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&a,&b,&n);
        factor();
        printf("Case #%d: %lld\n",++cas,b-a+1-solve(b)+solve(a-1));
    }
    return 0;
}

(1)：因为组合数的表示：
C(k,0)+C(k,1)+…+C(k,k)=2^k
又因为题目中，至少要取1个数，所以用<,一个数表示一个可能情况。
(2)
对取得每种情况进行分析，
取一定数目的数时，对应了多个i,而对于每个i,通过这个操作刚好可以求出此时i对应的是所选择的哪几个数，而且不重复。（神奇之处）