QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693159 | #7735. Primitive Root | konghaojie# | TL | 0ms | 0kb | C++17 | 649b | 2024-10-31 15:38:21 | 2024-10-31 15:38:57 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef unsigned long long ull;
const ull MAX=4e18;
const int D=500;
void solve(){
int p,m;cin>>p>>m;
ull l=0,r=MAX/p;
while(l<=r){
int mid=(l+r)>>1;
int num=(1+r*p)^(p-1);
if(num>m) r=mid-1;
else l=mid+1;
}
ull ind=r;
int ans=0;
l=ind-D,r=ind+D;
if(l<0) l=0;
if(r>MAX/p) r=MAX/p;
for(int i=l;i<=r;i++){
int num=(1+i*p)^(p-1);
if(num<=m) ans++;
}
ans+=l;
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 0 7 11 1145141 998244353