本文主要是介绍HDU 3641 Treasure Hunting，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题貌似是10年杭州网络赛的题，乍一看挺唬人的，数据范围那么大。实际上就是个简单数论，看完题就想到解法了，只不过细节上要注意很多。
下面是详细解法：
a1^b1*a2^b2*a3^b3…*an^bn ，对于这个序列，我们把每个a都质因子分解，然后整个序列中质因子的种类和个数就都知道了，然后就要求X了，对于某个X的阶乘中含有的某个质因子的个数，这个有个很简单的结论，也很好理解,log(n)时间内就能得出结果，不知道的可以去面壁了。
for(k = factor; k <= x; k *= factor)
sum+= x/k;
大概就是这样子，其中factor是质因子，sum就是x!的该因子的个数了。
然后呢，就是二分答案了。
二分上限也是很有讲究的，可以自己根据输入的数据求出个上限，不过对于所有数据来说，因为100以内最大的质数貌似是97吧，极限数据应该是全是97，b都是最大，那么只要满足这种情况，所有情况的上限都可以在范围内了，我就先写了个程序跑出了上限，而且我发现，直接开到2^63-1之类的数是不行的，中间会出现溢出。
二分过程中，就判断x!的所有因子数是不是都能满足给出的序列中所要求的因子数。满足的话，肯定能整除了，然后逐渐缩小范围。
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 205
#define INF 100000000
#define eps 1e-9
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
bool tag[101];
__int64 p[101];
int cnt = 0;
void get_prime() //线性筛素数
{cnt = 0;for (__int64 i = 2; i < 101; i++){if (!tag[i])p[cnt++] = i;for (__int64 j = 0; j < cnt && p[j] * i < 101; j++){tag[i*p[j]] = 1;if (i % p[j] == 0)break;}}
}
__int64 a[105];
__int64 b[105];
__int64 num[105];
__int64 tmp[105];
int main()
{//freopen("d:/data.in","r",stdin);//freopen("d:/data.out","w",stdout);__int64 sum = 0;__int64 i, j;int t, n;scanf("%d", &t);get_prime();while(t--){memset(num, 0, sizeof(num));__int64 high = 96000000099999999LL; //二分上限__int64 low = 0LL;scanf("%d", &n);for(i = 0; i < n; i++){scanf("%I64d%I64d", &a[i], &b[i]);for(j = 0; j < cnt && p[j] * p[j] <= a[i]; j++) //对a[i]因子分解{__int64 ct = 0;if(a[i] % p[j] == 0){while(a[i] % p[j] == 0){ct++;a[i] /= p[j];}}num[p[j]] += ct * b[i];}if(a[i] > 1){num[a[i]] += b[i];}}__int64 ans = 0;while(low <= high){__int64 mid = (low + high) / 2;memset(tmp, 0, sizeof(tmp));for(i = 0; i < cnt && p[i] < 100; i++){for(j = p[i]; j <= mid; j *= p[i]){tmp[p[i]] += mid / j;}}int big = 0;for(i = 0; p[i] < 100; i++){if(num[p[i]] == 0) continue;if(num[p[i]] > tmp[p[i]]){big = -1;break;}}int cn = 0;for(i = 0; p[i] < 100; i++)if(num[p[i]] > 0) cn++;int nc = 0;for(i = 0; p[i] < 100; i++){if(num[p[i]] == 0) continue;if(tmp[p[i]] >= num[p[i]]) nc++;}if(nc == cn) big = 1;if(big == 0)break;else if(big == -1){low = mid + 1;}else if(big == 1){high = mid - 1;}}printf("%I64d\n", low);}return 0;
}这篇关于HDU 3641 Treasure Hunting的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
