出题人题解 | #小y的质数#

原题解链接：https://ac.nowcoder.com/discuss/181037

首先换个姿势看这个问题

求有多少个$xx$满足，并且$gcd(x,x+2k)=1gcd(x,x+2k)=1$

众所周知，$gcd(x,x+2k)=1gcd(x,x\; +\; 2k)=1$与$gcd(x,2k)=1gcd(x,2k)=1$等价。

所以问题转化为求区间$[L,R-2k][L,R\; -\; 2k]$内有多少$xx$满足$gcd(x,2k)=1gcd(x,2k)=1$

因为区间比较大。所以可以对$2k2k$分解质因子。

然后容斥一下公因数，假设当前枚举到的质因子个数为$ii$。那就暴力搜索出来所有可能的公因数。然后计算$[L,R][L,R]$内为当前公因数倍数的数字个数。然后容斥就行了。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define int ll
ll read() {
   ll x = 0, f = 1;
   char c = getchar();
   while(c < '0' || c > '9') {
      if(c == '-') f = -1;
      c = getchar();
   }
   while(c >= '0' && c <= '9') {
      x = x * 10 + c - '0';
      c = getchar();
   }
   return x * f;
}
const int N = 4000000 + 100;
int prime[N],tot;
void fz(ll x) {
   for(ll i = 2;i * i <= x;++i) {
      if(x % i == 0) prime[++tot] = i;
      while(x % i == 0) x /= i;
   }
   if(x != 1) prime[++tot] = x;
}
int js,tmp[N];
void get(int pos,int sy,int now) {
   if(!sy) {
      tmp[++js] = now;
      return;
   }
   if(pos == tot + 1) return;
   get(pos + 1,sy - 1,now * prime[pos]);
   get(pos + 1,sy,now);
}
ll L,R,K;
ll work(ll x) {
   return R / x - (L - 1) / x;
}
 signed main() {
    L = read(),R = read(),K = read();
   K *= 2;
   L += K;
   if(L > R) {
      puts("0");
      return 0;
   }
   fz(K);
   sort(prime + 1,prime + tot + 1);
   ll ans = 0;
   for(int i = 1;i <= tot;++i) {
      int k;
      if(i & 1) k = 1;else k = -1;
      js = 0;
      get(1,i,1);
      for(int j = 1;j <= js;++j) {
         ans += k * work(tmp[j]);
      }
   }
   cout << R - L + 1 - ans;
   return 0;
}