找出（l，r）內(nèi)的所有的指數(shù)最大的次方和

因?yàn)橐粋€(gè)數(shù)可能可以看成a^b和c^d，所以我需要去重，從后往前枚舉冪數(shù)，然后找可以整除的部分，把低次冪的數(shù)去掉。

然后開n方的部分，先用pow()函數(shù)找到最接近答案的數(shù)，但是會(huì)丟失精度，然后在這個(gè)數(shù)的附近尋找最接近答案的整數(shù)，用快速冪在乘n次冪回去，看最接近原本數(shù)的是哪一個(gè)。

#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 = 100; const int maxm = 200010; const int mod = 998244353; const double eps = 1e-8; using namespace std;ll n, m; int T, tol; ll num[70]; ll INF = 1e18;ll qpow(ll a, ll b) {ll ans = 1;while(b) {if(b&1) {double tmp = 1.0 * INF / ans;if(a > tmp) return -1;ans = ans * a;}b >>= 1;if(a > ((ll)1<<31) && b) return -1;a = a*a;}return ans; }ll calc(ll x, int pos) {ll a = (ll)pow((double)x, 1.0/pos);ll ansl = qpow(a-1, pos);ll ansm = qpow(a, pos);ll ansr = qpow(a+1, pos);if(ansr != -1 && ansr <= x) return a+1;if(ansm != -1 && ansm <= x) return a;return a-1; }ll solve(ll x) {memset(num, 0, sizeof num);num[1] = x;int pos = 2;for(; pos <= 64; pos++) {ll tmp = calc(x, pos) - 1;if(tmp <= 0) break;num[pos] = tmp;}pos--;for(int i=pos; i>=1; i--) {for(int j=2; 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 = 0;for(int i=1; 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-1);printf("%I64d\n", ans);}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jiaaaaaaaqi/p/9473284.html

總結(jié)

以上是生活随笔為你收集整理的Integer’s Power HDU - 3208（容斥原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。