找出(l,r)内的所有的指数最大的次方和
因为一个数可能可以看成a^b和c^d,所以我需要去重,从后往前枚举幂数,然后找可以整除的部分,把低次幂的数去掉。
然后开n方的部分,先用pow()函数找到最接近答案的数,但是会丢失精度,然后在这个数的附近寻找最接近答案的整数,用快速幂在乘n次幂回去,看最接近原本数的是哪一个。
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int mod = ;
const double eps = 1e-;
using namespace std; ll n, m;
int T, tol;
ll num[];
ll INF = 1e18; ll qpow(ll a, ll b) {
ll ans = ;
while(b) {
if(b&) {
double tmp = 1.0 * INF / ans;
if(a > tmp) return -;
ans = ans * a;
}
b >>= ;
if(a > ((ll)<<) && b) return -;
a = a*a;
}
return ans;
} ll calc(ll x, int pos) {
ll a = (ll)pow((double)x, 1.0/pos);
ll ansl = qpow(a-, pos);
ll ansm = qpow(a, pos);
ll ansr = qpow(a+, pos);
if(ansr != - && ansr <= x) return a+;
if(ansm != - && ansm <= x) return a;
return a-;
} ll solve(ll x) {
memset(num, , sizeof num);
num[] = x;
int pos = ;
for(; pos <= ; pos++) {
ll tmp = calc(x, pos) - ;
if(tmp <= ) break;
num[pos] = tmp;
}
pos--;
for(int i=pos; i>=; i--) {
for(int j=; i*j<=pos; j++) {
num[i] -= num[i*j];
}
}
//for(int i=1; i<=pos; i++) printf("%I64d%c", num[i], i==pos ? '\n' : ' ');
ll ans = ;
for(int i=; i<=pos; i++) ans += i * num[i];
return ans;
} int main() {
while(scanf("%I64d%I64d", &n, &m), n||m) {
ll ans = solve(m);
ans -= solve(n-);
printf("%I64d\n", ans);
}
return ;
}