首页 > ACM题库 > HDU-杭电 > HDU 3641-Treasure Hunting-分治-[解题报告]HOJ
2014
11-30

HDU 3641-Treasure Hunting-分治-[解题报告]HOJ

Treasure Hunting

问题描述 :

Zstu_yhr is a very curious person who fell in love with math when he was in elementary school phase. When he entered the middle school, he learned Multiplication and Power Multiplication. yhr is so ambitious that he not only dreams to be a mathematician but also dreams to be richer than Bill Gates.
One day, he is suddenly encountered with a crazy thought that is to hunt treasure to make one of his dreams a reality. Since yhr is such a strong-willed person that he will never give up as long as his goal has not been achieved. After going through 9*9 challenges, as a reward of god for that hard, he finally discovers an antique hole which is very likely to have a good number of treasures in it. However, as every novel writes, he can never get the treasures so easily. He has to open a coded door at first. He finds that there are 2*N numbers on the door. He speculates that they must be able to generate the password. Disappointedly, there isn’t any clue left for him. He has no better way but to YY. Firstly, he divides these 2*N number into N piles equally. The first pile is composed of a1,b1 and the second pile is composed of a2,b2…certainly, the i-th pile is composed of ai,bi…After completing this task, he calculates a1^b1*a2^b2*a3^b3…*an^bn and gets its result M. He takes M as the password to open the door. What’s a pity, he fails. Then he starts to YY again. Maybe the right password is the minimum number x which satisfies the equation x!%M=0. So he wants to have a try. But he doesn’t know how to get the number so that he has to turn to you for help. Can you help him?

输入:

In the first line is an integer T (1<=T<=50) indicating the number of test cases.
Each test case begins with an integer n (1<=n<=100), then followed n lines. Each line contains two numbers ai and bi (1 <= ai <= 100, 1<=bi<=10000000000000)

输出:

In the first line is an integer T (1<=T<=50) indicating the number of test cases.
Each test case begins with an integer n (1<=n<=100), then followed n lines. Each line contains two numbers ai and bi (1 <= ai <= 100, 1<=bi<=10000000000000)

样例输入:

1
2
3 2
4 1

样例输出:

6

Hint
n! is the factorial of number n: 0!=1 n!=n*(n-1)! (n>=1) a^0=1 (a>=1) a^i=a*(a^i-1) (i>=1)

题意,告诉你一个数m,求最小的x!满足x!%m== 0;

解:

       将m的所有质数因子和质数因子的个数存起来。二分x,对于每个m的质因子p,x!的p的个数都大于等于m的质因子个数就行了。对于二分的上限还是得注意的。就因为这个wa了一个。二分的下限也得注意,从0开始。

      二分真是好神!记得对于大数要写LL。

/*
Pro: 0

Sol:

date:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 99999999999999999999LL
using namespace std;
int prime[30],sub;
__int64 num[110];
void getprime(){
    bool flag[111] ;    sub = 0;
    memset(flag , true, sizeof(flag));
    for(int i = 2; i <= 110; i ++)
        for(int j = i + i; j <= 110;j += i)
            flag[j] = false;

    for(int i = 2; i <= 100; i ++)
        if(flag[i]) prime[sub ++] = i;
}
__int64 getnum(__int64 x, int p){//
    __int64 sum = 0;
    while(x % p == 0){
        sum ++;
        x /= p;
    }return sum;
}
bool can(__int64 indx){
    for(int i = 0; i < sub; i ++){
//        printf("%d   %d\n",i,prime[i]); 我还以为又是数组越界的奇怪问题呢,原来是这个函数被多次调用
        if(prime[i] && num[prime[i]]){
            __int64 sum = 0;
            for(__int64 k = prime[i]; k <= indx; k *= prime[i])
                sum += indx / k;
            if(sum < num[prime[i]]) return false;
        }
    }
    return true;
}
__int64 bin(){
    __int64 low = 0, high = inf, mid ;
    while(low <= high){
        mid = (low + high) >> 1;
//         printf("%d&&\n",mid);
        if(can(mid))    high = mid - 1;
        else low = mid + 1;
    }
    return low;
}
int main(){
    getprime();
//    __int64 kk = 10000000000000 * 100;  __int64 sum = 0;
//                  99999999999999999999
//    __int64 in  = 33333333333333333333;
//    for(__int64 ka = 97; ka <= in; ka *= 97)
//        sum += in / ka;
//    if(sum >= kk) puts("yes");
//    else puts("no");

    int t,n,a;  __int64 b;
    scanf("%d",&t);
    while(t -- ){
        scanf("%d",&n);
        memset(num,0,sizeof(num));
        for(int i = 0; i < n; i ++){
            scanf("%d%I64d",&a,&b);
            for(int j = 0; j < sub; j ++){
                if(a % prime[j] == 0){
                    num[prime[j]] += getnum(a,prime[j]) * b;
                }
            }
        }
        printf("%I64d\n",bin());
    }
    return 0;
}

参考:http://blog.csdn.net/julyana_lin/article/details/7916286


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?