博客

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

≤ 10

6).

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即可

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
ll sol(ll x,vector<ll>&f){
    ll res=0;
    int n=(int)f.size();
    for(int i=1;i<(1<<n);i++)
    {
        ll now=1,sgn=-1;
        for(int j=0;j<n;j++)
            if(i&(1<<j))now*=f[j],sgn*=-1;
        res+=sgn*(x/now);
    }
    return x-res;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll x,p,k;
        scanf("%lld%lld%lld",&x,&p,&k);
        vector<ll>g;
        for(ll i=2;i*i<=p;i++){
            if(p%i==0){
                g.push_back(i);
                while(p%i==0){
                    p/=i;
                }
            }
        }
        if(p>1)g.push_back(p);
        ll r=1000000000000LL;
        ll l=0;
        k+=sol(x,g);
        ll ans;
        while(l<=r){
            ll mid=(l+r)/2;
            if(sol(mid,g)>=k){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}