首页 > ACM题库 > HDU-杭电 > HDU 1842 Gorilla.bas-快速幂-[解题报告] C++
2013
12-23

HDU 1842 Gorilla.bas-快速幂-[解题报告] C++

Gorilla.bas

问题描述 :

Maybe you remember the old QBasic game gorilla.bas. But in case you don’t, the game was about two gorillas who were throwing explosive bananas at each other. Each gorilla was controlled by one of the two players. Each player could choose the angle and speed of the shot and the banana would follow a parabolic trajectory. As if finding the appropriate angle and speed in order to hit the opponent’s gorilla wasn’t difficult enough, there were also buildings which could block the banana’s trajectory.

This time you are close to the end of a game where, coincidentally, both gorillas were located at the same height (equal to 0). So, to be more precise, your gorilla is a point located at coordinates (0,0) and the opponent’s gorilla is located at the coordinates (d,0). Between the two gorillas there are N buildings (vertical line segments), having different heights. You want to finish the game as soon as possible so you want this shot to be the last one. Therefore, the banana (which is also a point) should be thrown in such a way that it should hit the opponent’s gorilla, but not the buildings (although it may touch the top of any building). Furthermore, in order to prove your superior skills to your opponent, you want to choose the minimum speed v for throwing the banana (but you may choose any angle u between 0 and π/2).
When solving this problem, you should make use of the value of the gravitational acceleration g (given as part of the input) and the following laws of motion:

输入:

The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 3 numbers, separated by blanks: an integer d (1<=d<=1.000.000), a floatin point number g (1<=g<=10) and an integer N (0<=N<=50.000). The ith of the next N lines contains two integer numbers, separated by one blank: Xi (1<= Xi<d) and Hi (1<=Hi<=1.000.000). Xi is the X coordinate of the ith building and Hi is its height. Furthermore, Xi<Xi+1.

输出:

For each of the T test cases print one line containing the minimum value of the speed required to throw the banana. Print this value with 3 decimal digits, rounded (up or down) according to the 4th decimal digit.

样例输入:

2
1 9.8 0
1000 1 1
500 10000

样例输出:

3.130
141.466

Raising Modulo Numbers

#include <iostream>
using namespace std;
//计算a^bmodn
int modexp(int a,int b,int n)
{
    int ret=1;
    int tmp=a;
    while(b)
    {
       //基数存在
       if(b&0x1) ret=ret*tmp%n;
       tmp=tmp*tmp%n;
       b>>=1;
    }
    return ret;
}
int main()
{
    int Z,M,H,a,b,ans;
    cin >> Z;
    while(Z--)
    {
       ans=0;
       cin >> M >> H;
       while(H--)
       {
           cin >> a >> b;
           ans+=modexp(a%M,b,M);//我表示不懂这儿,是看别人写的,我觉得是(a1^b1+.....)%M=(a1^b1)%M+...为什么是((a%M)^b)%M+....?求解释!
           //(a+b)%c=(a%c+b%c)%c
       }
       cout << ans%M << endl;
    }
    return 0;
}

思路

《算法导论》也有!

发帖问啦,明白啦!!

(a+b)%c=(a%c+b%c)%c那么是不是(a1+a2+…)%c=(a1%c+a2%c+…)%c?

求证明过程!!!

不是一般性,设

a1 = m1*c + n1 => a1%c = n1

a2 = m2*c + n2 => a2%c = n2



an = mn*c + nn => an%c = nn

其中n1,n2…,nn都属于半开半闭区间[0,c)



那么

(a1+a2+...an)%c  

= [(m1+m2+...mn)*c + (n1+n2+...nn)]%c

= (n1+n2+…nn)%c

= (a1%c + a2%c + … +an%c)%c

解题报告转自:http://blog.csdn.net/hit1110310422/article/details/8026190


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks