https://codeforc.es/contest/920/problem/G G. List Of Integers time limit per test 5 seconds memory limit per test 256 megabytes input standard input output standard output
Let's denote as L(x, p) an infinite sequence of integers y such that gcd(p, y) = 1 and y > x (where gcd is the greatest common divisor of two integer numbers), sorted in ascending order. The elements of L(x, p) are 1-indexed; for example, 9, 13 and 15 are the first, the second and the third elements of L(7, 22), respectively.
You have to process t queries. Each query is denoted by three integers x, p and k, and the answer to this query is k-th element of L(x, p).
Input
The first line contains one integer t (1 ≤ t ≤ 30000) — the number of queries to process.
Then t lines follow. i-th line contains three integers x, p and k for i-th query (1 ≤ x, p, k ≤ 106).
Output
Print t integers, where i-th integer is the answer to i-th query.
Examples input Copy
3
7 22 1
7 22 2
7 22 3
output Copy
9
13
15
input Copy
5
42 42 42
43 43 43
44 44 44
45 45 45
46 46 46
output Copy
187
87
139
128
141
題意:求出與p互質并且>x的第k小數
題解:首先求出p所有的質因子,狀壓枚舉出質因子相乘的情況,比如000001表示隻有一個最小的質因子,則在1-y中有y/prime[1]個,再通過容斥即可求出與p不互質的個數,此時二分答案y即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define debug(x) cout<<#x<<" is "<<x<<endl;
4 typedef long long ll;
5 ll sol(ll x,vector<ll>&f){
6 ll res=0;
7 int n=(int)f.size();
8 for(int i=1;i<(1<<n);i++)
9 {
10 ll now=1,sgn=-1;
11 for(int j=0;j<n;j++)
12 if(i&(1<<j))now*=f[j],sgn*=-1;
13 res+=sgn*(x/now);
14 }
15 return x-res;
16 }
17 int main(){
18 int t;
19 scanf("%d",&t);
20 while(t--){
21 ll x,p,k;
22 scanf("%lld%lld%lld",&x,&p,&k);
23 vector<ll>g;
24 for(ll i=2;i*i<=p;i++){
25 if(p%i==0){
26 g.push_back(i);
27 while(p%i==0){
28 p/=i;
29 }
30 }
31 }
32 if(p>1)g.push_back(p);
33 ll r=1000000000000LL;
34 ll l=0;
35 k+=sol(x,g);
36 ll ans;
37 while(l<=r){
38 ll mid=(l+r)/2;
39 if(sol(mid,g)>=k){
40 ans=mid;
41 r=mid-1;
42 }
43 else{
44 l=mid+1;
45 }
46 }
47 printf("%lld\n",ans);
48 }
49 return 0;
50 }
View Code
轉載于:https://www.cnblogs.com/MekakuCityActor/p/10926041.html