HDU 5297

用x ^ (1 / n) 来求个数,容斥原理 , Num会向后移动, 迭代到不再变化,退出循环HDU 5297

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int Primes[] = {-2,-3,-5,-7,-11,-13,-17,-19,-23,-29,-31,-37,-41,-43,-47,-53,-59,-61,-67,-71};
vector<int> R_number;
void GetR(LL R) {
R_number.clear();
for(int i = 0; abs(Primes[i])<= R; ++i) {
int tmp = Primes[i];
int Num = R_number.size();
for(int j = 0; j < Num; ++j) {
if(abs(R_number[j]*tmp) <= 63)
R_number.push_back(tmp * R_number[j]);
}
R_number.push_back(Primes[i]);
}
}
LL Cnt(LL N) {
//GetR(R);
if(N == 1) return 0;
LL cnt = N;
for(int i = 0; i < R_number.size(); ++i) {
LL tmp = LL (pow(N+0.5, 1.0/abs(R_number[i])) - 1);
if(R_number[i] < 0) cnt -= tmp;
else cnt += tmp;
}
return cnt - 1;
}
void Solve(LL N,LL R) {
GetR(R);
LL ans = N;
while(1) {
LL tmp = Cnt(ans);
if(tmp == N) break;
ans += N - tmp;
}
printf("%lld\n",ans);
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
LL n,r;
scanf("%I64d %I64d",&n,&r);
Solve(n,r);
}
return 0;
}
上一篇:【Linux网络编程】TCP网络编程中connect()、listen()和accept()三者之间的关系


下一篇:Beta阶段冲刺-3