求大于(x)的数里面，第(k)个与(p)互质的数
进行二分，二分数字，那么对于每一个数字(mid)，可以查询([x + 1, mid])里面有多少个数与(p)互质，如果个数是(k)，那么答案就是(mid)
问题转换为求([1,n])有多少个数与(p)互质
模板题
把(p)进行唯一分解定理分解，然后对于质因子进行容斥。最多有(7)个质数，那么容斥的时间复杂度是(O(2^7*7))
在容斥里面因为是质数求lcm，所以不用lcm，直接乘就行了。
#include <bits/stdc++.h>
#define ll long long
#define CASE int Kase = 0; cin >> Kase; for(int kase = 1; kase <= Kase; kase++)
using namespace std;
template<typename T = long long> inline T read() {
T s = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
return s * f;
}
const int N = 1e5 + 5, M = 1e6 + 5, MOD = 1e9 + 7, CM = 998244353, INF = 0x3f3f3f3f;
int pri[N], tot;
void divi(int n){
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
pri[++tot] = i;
while(n % i == 0) n /= i;
}
}
if(n > 1) pri[++tot] = n;
}
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b){
return a / gcd(a, b) * b;
}
ll cal(ll l, ll r, int p){ // [l, r]多少个数与p互质
ll ans = 0;
for(int i = 1; i < (1 << tot); i++) {
int k = 0; ll lc = 1;
for(int j = 0; j < tot; j++) {
if(i & (1 << j)) {
k++; lc = lc * pri[j + 1];
}
}
if(k & 1) ans += r / lc - (l - 1) / lc;
else ans -= r / lc - (l - 1) / lc;
}
return r - l + 1 - ans;
}
bool check(int mid, int x, int p, int k){
if(mid <= x) return 0;
int num = cal(x + 1, mid, p);
return num >= k;
}
void solve(int kase){
int x = read(), p = read(), k = read();
tot = 0;
divi(p);
int l = 1, r = 1e9;
while(r - l >= 1) {
int mid = (l + r) >> 1;
if(check(mid, x, p, k)) r = mid;
else l = mid + 1;
}
printf("%d
", r);
}
const bool DUO = 1;
int main(){
clock_t start, finish; double totaltime; start = clock();
if(DUO) {CASE solve(kase);} else solve(1);
finish = clock();
#ifdef ONLINE_JUDGE
return 0;
#endif
printf("
Time: %lfms
", (double)(finish - start) / CLOCKS_PER_SEC * 1000);
return 0;
}
还有一道题，也有点像
求[1, n!]里与(m!)互质的数字个数，对一个质数(p)取模
传送门
结论：
对于两个正整数 (m) 和 (n,) 如果 (n) 是 (m) 的倍数，那么 (1
ightarrow n) 中与 (m) 互素的数的个数为(frac{n}{m} phi(m))
因为(gcd(a, b) = gcd(a + k * b, b))，(k)是正整数
那直接用定义法求出(varphi(m!))，线性筛一下质数。(m!)的质因子就是([1,m])里的所有质数。
#include <bits/stdc++.h>
#define ll long long
#define CASE int Kase = 0; cin >> Kase; for(int kase = 1; kase <= Kase; kase++)
using namespace std;
template<typename T = long long> inline T read() {
T s = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
return s * f;
}
const int N = 1e7 + 5, M = 1e6 + 5, MOD = 1e9 + 7, CM = 998244353, INF = 0x3f3f3f3f;
int mod;
int pri[N], tot;
bool vis[N];
ll ksm(ll a, ll b, ll p){
ll ans = 1; a %= p;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
void pri_table(int n){
vis[0] = vis[1] = 1;
for(int i = 2; i <= n; i++) {
if(!vis[i]) pri[++tot] = i;
for(int j = 1; j <= tot; j++) {
if(i * pri[j] > n) break;
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
int fac[N], inv[N];
void solve(){
int n = read(), m = read();
int phi = 1ll * fac[m] * inv[m] % mod;
int facc = 1ll * fac[n] * ksm(fac[m], mod - 2, mod) % mod;
int ans = 1ll * facc * phi % mod;
printf("%d
", ans);
}
int main(){
pri_table(N - 5);
int t = read(); mod = read();
fac[0] = 1, inv[0] = 1;
for(int i = 1; i <= N - 4; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
for(int i = 1; i <= N - 4; i++) {
if(!vis[i]) {
inv[i] = ksm(i, mod - 2, mod);
inv[i] = 1ll * (1 - inv[i] + mod) % mod;
inv[i] = 1ll * inv[i - 1] * inv[i] % mod;
}else inv[i] = inv[i - 1];
}
for(int i = 1; i <= t; i++) solve();
return 0;
}