首页 > 代码库 > poj 3134Power Calculus (IDAstar)

poj 3134Power Calculus (IDAstar)

2024-11-15 16:15:40   203人阅读


Power Calculus
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 1760 Accepted: 947

Description

Starting with x and repeatedly multiplying by x, we can computex31 with thirty multiplications:

x2 = x × x, x3 = x2 × x, x4 = x3 ×x, …,x31 = x30 × x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to computex31 with eight multiplications:

x2 = x × x, x3 = x2 × x, x6 = x3 ×x3,x7 = x6 × x,x14 =x7 × x7, x15 =x14 ×x, x30 = x15 ×x15,x31 = x30 × x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x × x, x4 = x2 ×x2,x8 = x4 × x4,x8 =x4 × x4, x10 =x8 ×x2, x20 = x10 ×x10,x30 = x20 × x10, x31 = x30 × x.

If division is also available, we can find a even shorter sequence of operations. It is possible to computex31 with six operations (five multiplications and one division):

x2 = x × x, x4 = x2 × x2, x8 = x4 ×x4,x16 = x8 × x8,x32 =x16 × x16, x31 = x32 ÷ x.

This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to computexn by multiplication and division starting withx for the given positive integern. Products and quotients appearing in the sequence should bex to a positive integer’s power. In others words,x?3, for example, should never appear.

Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to computexn starting withx for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Sample Input

1
31
70
91
473
512
811
953
0

Sample Output

0
6
8
9
11
9
13
12



代码:

#include<iostream>
#include<cstdio>
using namespace std;
int T;
const int mod = 1e9+7;
long long int pow(int num,int coun)
{
    long long int p=num,q=coun,ret=1;
    while(q)
    {
        if(q & 1)  {
            ret=ret*p%mod;
        }
        q>>=1;
        p=p*p%mod;
    }
    return ret;
}
int main(){
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        if(n==k){printf("1\n");continue;}
        if(n<k){printf(("0\n"));continue;}
        if(n==k+1){printf("2\n");continue;}
        printf("%I64d\n",pow(2,(n-k-2))*(n-k+3)%mod);
    }
}


poj 3134Power Calculus (IDAstar)


联系
我们