牛客练习赛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;
void pre() {
mark = mark = mark = mark = mark = mark = mark = mark = 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, t = 0;
for (int i = 2; i <= m; i++)
if (mark)//m内质数
v = 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;
}
ll s = (cnt & 1) ? -1 : 1;//奇数个时mu为负
h += s * n / tmp;
}
bool flag = (min(h + k - 1, n) >= q);
puts(flag ? "Yes" : "QAQ");
}
}
文档来源：51CTO技术博客https://blog.51cto.com/u_14696602/3107445
页:
[1]