本文主要是介绍HDU 3208 Integer’s Power 指数和、容斥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
输入l，r，求出[l, r]区间内，表示成指数形式的指数和。
要求a^b，a尽量小，b尽量大。例如，16应该表示成2^4，而不是4^2。
思路：
参考自：http://blog.csdn.net/acdreamers/article/details/10977785
这算是容斥吧？初学的我也不大懂。
如果我们可以知道每个指数所表示的个数，那么问题就可以解决了。
感觉像动态规划，于是数组名就那样了。dp[i]：指数为i的个数。
1.对于每个i（由于2^60>1e18，因此 i 最大为60 即可）进行初始化：dp[i] = 。
2.可以看到dp[2]里面包含了指数表示为4，6，8……的个数，因此现在就是要把这些能够表示成更高次方的容斥出去（具体做法看代码）。
*这题卡pow的精度，因此要注意，我直接采用参考题解里的方法解决。
pow的精度不会误差误会超过1，因此测试x-1，x，x+1。
code：
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;typedef long long LL;
const double eps = 1e-9;
const double INF = (double)1e18+300;LL a[65];
LL mul(LL tt, LL i)
{LL ret = 1, a = tt;while(i){if(i&1){double tmp = INF/ret;if(a>tmp) return -1;ret *= a;}i >>= 1;if(a>(1e9)&&i>0) return -1;a = a*a;}return ret;
}LL check(LL tt, LL t, int i)
{//ttLL tmp = mul(tt, i);if(tmp == t) return tt;//tt-1;if(tmp > t || tmp == -1) return tt-1;//tt+1;else if(tmp < t){tmp = mul(tt+1, i);if(tmp != -1 && tmp <= t) return tt+1;}return tt;
}LL calc(LL t)
{if(t < 2) return 0;memset(a, 0, sizeof(a));int cnt = 1;a[1] = t-1;for(int i = 2;i <= 60; i++){LL tt = (LL)(pow((double)t, 1.0/i)+eps);tt = check(tt, t, i);if(tt-1 == 0) break;a[i] = tt-1;cnt = i;}for(int i = cnt;i > 1; i--)for(int j = 1;j < i; j++)if(i%j==0) a[j]-=a[i];LL ret = 0;for(int i = cnt;i >= 1; i--)ret += a[i]*i;return ret;
}int main()
{ios::sync_with_stdio(false);LL l, h;while(cin>>l>>h&&l)cout<<calc(h)-calc(l-1)<<endl;return 0;
}这篇关于HDU 3208 Integer’s Power 指数和、容斥的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
