1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std ;
int p[1000000];
int num;
void pr(long long x)      //求x的质因子
{
    num = 0;
    for (long long i = 2 ; i <= x/i ; i++)
    {
        if (x % i == 0)
        {
            p[num++] = i;
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        p[num++] = x;
}
long long solve(long long n)        //1~n中不与k互质的数
{
    long long ans = 0;
    for (long long i = 1; i < (long long)1 << num ; i++)       //其二进制位为1，表示这些质因数被用到
    {
        int ant = 0;        //用奇数个质因数加，偶数个减
        long long t = 1;
        for (int j = 0 ; j < num ; j++)
        {
            if (((long long )1 << j) & i)
            {
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX