恒纪元【算法赛】

恒纪元【算法赛】

主要思路就是先求出所有的乱纪元，然后使用二分查找找到下一个恒纪元

#include <bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 1e6+7;
#define int long long 
typedef long long ll;
const int M=1e12;
int a[N];
int index1=1;
set<int>se;
int qpow(ll a, ll b) {ll ans = 1;while (b) {if (b & 1)ans = ans * a ;a = a * a ;b >>= 1;}return ans ;
}
//string s;
int n,m;
int check(int s){int l=1,r=index1-1;while(l<r){int mid=l+r>>1;if(a[mid]==s)return mid;if(a[mid]>s)r=mid-1;if(a[mid]<s)l=mid+1;}
}
signed main()
{IOS; int x,y,z;cin>>x>>y>>z;for(int i=0;i<=64;i++){for(int j=0;j<=64;j++){
for(int k=0;k<=64;k++){if(pow(x,i)+pow(y,j)+pow(z,k)<=M)se.insert(pow(x,i)+pow(y,j)+pow(z,k));else break;}}}for(auto i:se){// cout<<i<<endl;a[index1++]=i;
}int q=0;cin>>q;while(q--){int s;cin>>s;int k= check(s);for(int t=k;;t++){if(a[t]+1!=a[t+1]){cout<<a[t]+1<<" "<<a[t+1]-a[t]-1<<endl;break;}}}return 0;
}