牛客练习赛43F（推式子）

青衣

要点

• 题目链接
  
• 1e18的数据无法\(O(n)\)的容斥，于是推式子，官解，其中式子有点小错误
  
• 不必预处理mu，直接按照素数的个数判断正负即可
  

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
ll k, q, n, m;
int mark[25];
void pre() {
  mark[2] = mark[3] = mark[5] = mark[7] = mark[11] = mark[13] = mark[17] = mark[19] = 1;
}
int main() {
  pre();
  for (scanf("%d", &T); T--;) {
    scanf("%lld %lld %lld %lld", &k, &q, &n, &m);
    if (!k) {//特判
      puts("QAQ"); continue;
    }
    ll h = n, P = 1;
    int v[10], t = 0;
    for (int i = 2; i <= m; i++)
      if (mark[i])//m内质数
        v[t++] = i, P *= i;
    for (int i = 1; i < (1 << t); i++) {//枚举组合
      int tmp = 1, cnt = 0;
      for (int j = 0; j < t; j++) {
        if ((i >> j) & 1)
          cnt++, tmp *= v[j];
      }
      ll s = (cnt & 1) ? -1 : 1;//奇数个时mu为负
      h += s * n / tmp;
    }
    bool flag = (min(h + k - 1, n) >= q);
    puts(flag ? "Yes" : "QAQ");
  }
}