2 3 3 4 4 5 5 6 36123 1
2374859 3029382 17 1 3 18132 样例输出 2 13195 13 翻译： 描述
人们都不同。有些人私下的看满是令人感兴趣的美女图片的杂志，一些人在他们地下室造炸弹，一些人喜欢使用窗户，一些人喜欢复杂的数学游戏。最新的市场调查表明，市场部分太过低估，缺乏这样的游戏。这种游戏是这样的包含在KOKODDáKH。规则如下： 每个玩家选择两个数字Ai 和 Bi，在光滑的纸上写下他们。其他人不能看见这些数字，在给定的时间所有的玩家展示他们的数字给别人看。目标是决定所有的表达式AiBi的和对M取模。第一个得出答案的是胜利者。根据玩家的表达式，很有可能通过选择大的数来增加难度。
你应该写一个程序来计算结果，并且能够造出是谁赢家。 输入
第一行输入一个整数z表示有z组测试数据。每组数据第一行是一个整数M(1 <= M <= 45000)。所有表达式的和对M取模。下一行是玩家个数H(1<=H<=45000)。下面H行是每个玩家的两个数字Ai Bi，两个数不会同时为0 输出
每组数据输出一行表达式(A1B1 + A2B2 + ... + AHBH) mod M.的结果。
思路/方法：如果找常规方法算即使是64位整数也不够存储，所以我们需要快速取模的算法。这算法推起来不简单，这里就不讲为什么，记住这么做就行，下面代码也有注释，至少能保证你看得懂代码，至于为什么这么写，可以百度“快速取模”。 代码：
#include
long long quickMod(long long a, long long b, int m)//a的b次方 对 m取模 {
long long s = 1;
while(b)//b次方就循环b次 {
if(b&1)//等价于b%2，如果b是奇数 {
s = s * a % m;//乘以a后对m取模 b--; }
a = a * a % m; b >>= 1;//等价于b/= 2 } return s; }
int main() {
int z, m, h, i, j;
long long s, a, b; scanf(\ for(i = 0; i < z; i++) {
s = 0;
scanf(\ scanf(\ for(j = 0; j < h; j++) {
scanf(\ s = s + quickMod(a, b, m); s = s % m; }
printf(\ } return 0; }
12: Euclid's Game(简单博弈论) 描述
Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7): 25 7 11 7 4 7 4 3 1 3 1 0 an Stan wins. 输入
The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts. 输出
For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed. 样例输入 34 12 15 24 0 0 样例输出 Stan wins Ollie wins 翻译： 描述
两个玩家，Stan和Ollie，以两个自然数开始。Stan，第一个玩家，用两数中较大的数 减去 两数中较小数的倍数，保证非负数。第二个玩家Ollie对上个结果进行同样的处理。下一轮有是Stan，像这样轮流。直到其中一个玩家能使得较大的数字减成0，则那个玩家就赢了。例如，玩家开始的数字是(25,7): 25 7
11 7 4 7 4 3 1 3 1 0 Stan赢了。 输入
输入多组测试数据，每组一行两个正整数，Stan总是第一个开始。 输出
每组数据输出一行，谁赢了比赛。输入两个0 0就不处理结束运行。
思路/方法：这题还是需要找规律。 我们假设a<=b，如果a>b就交换a b。
1.很明显，如果a或者b为1，则Stan必胜。如果a==b则Stan也必胜。 2.如果b==2*a,显然Stan必胜。如果b>2*a,我们可以假设b%a=c,(c
如果(c,a)是必败态,则Stan肯定会将b减成c，这时是O面临此种情况，可使得O必败。如果(c,a)是必胜态，则S可减b，使得b（要知道b>2*a啊，那就是说b=n*a+c,其中n>=2）成为a+c,局面成为(a,a+c)，这是O只有一种选择，那就是将a+c减一个a（仔细想想，按照游戏规则，他真的没别的办法了），局面变成了Stan面临的(c,a)是一种必胜态，也就是说，当b>2*a的时候，无论(c,a)是必胜态还是必败态，S都必胜。
3.如果a< b < 2 * a。这时只有一种选择，但我们仍然不知道是否能赢，所以我们用递归就行了，注意递归(b-a, a)时下一个状态，即对手的状态，所以我们要取反才是自己的状态。
上面就包含了所有的情况，同样的当a > b时，也是一样的，选手是从中选择一个大的数减去小的，所以谁大无所谓。 代码：
#include
void swap(long long * a, long long * b) {
long long t; t = *a; *a = *b; *b = t; }
int game(long long a, long long b) {
if(a > b)//保证b较大 swap(&a, &b); if(a == b || b >= 2 * a) return 1; else
return !game(b - a, a);//下一个状态是对手状态，对手赢了自己就输了，所以需要加一个!才是自己的状态 }
int main() {
long long a, b;
while(scanf(\ if(game(a, b))
printf(\ else
printf(\ return 0; }
二．几何基础
1: 求两直线的夹角 描述
有两条直线，AB和CD，A、B、C、D的坐标已知，求这两条直线的所成夹角中较小的一个。 输入
输入包括多组数据，第一行为测试数据的组数n，接下来后面有n行，每一行有8个整数，依次代表A点的x坐标、A点的y坐标，B点的x坐标、B点的y坐标，C点的x坐标、C点的y坐标，D点的x坐标、D点的y坐标。 输出
输出夹角的近似值（角度值而非弧度值，保留1位小数）。 样例输入 2
0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 样例输出 90.0 45.0
思路/方法：两直线夹角等价于求两直线的向量的夹角。即cos
#include
int a[8], n, i, j, x1, x2, y1, y2;//两个向量(x1,y1)(x2,y2) double angle;//角度 scanf(\ for(i = 0; i < n; i++) {
for(j = 0; j < 8; j++)
scanf(\输入到数组中 x1 = a[2] - a[0]; y1 = a[3] - a[1]; x2 = a[6] - a[4]; y2 = a[7] - a[5];
angle = fabs((x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2)));//cos
2: 计算几何练习题——线段相交 描述
线段相交测试在计算几何中是经常用到的，给定线段P1P2（P1和P2是线段的两端点，且不重合）、P3P4（P3和P4是线段的两端点，且不重合），判断P1P2和P3P4是否相交。P1P2和P3P4不重合，即指只存在一个点P，它既落在P1P2上又落在P3P4上（含线段的端点）。 输入
输入数据有多组，第一行为测试数据的组数N，下面包括2N行，每组测试数据含2行，第一行为P1P2的坐标值，第二行为P3P4的坐标值，比如下面的数据
1 0 0 1 1 2 2 3 3
表示P1、P2、P3、P4的坐标分别为：P1（0,0），P2（1,1），P3（2,2），P4（3,3） 输出
判断每组数据中的线段P1P2和P3P4是否相交，如果相交输出YES，否则输出NO。每组数据输出占一行。 样例输入 1 0 0 1 1 2 2 3 3 样例输出 NO
思路/方法：判断线段相交，我这里介绍一种常见的方法。
快速排斥(两个由线段做对角线的矩形是否有交集) + 跨立(一个线段的两个端点在另一线段的两端) 判断是否有交集就是把所有不相交的情况取反，也就是
!( max(p1.x, p2.x) < min(p3.x, p4.x) || max(p3.x, p4.x) < min(p1.x, p2.x) || max(p1.y, p2.y) < min(p3.y, p4.y) || max(p3.y, p4.y) < min(p1.y, p2.y) )
判断跨立就是(AC X AB) * (AD X AB) <= 0 && (CA X CD) * (CB X CD) <= 0 叉乘X的公式是p1 X p2 = p1.x * p2.y - p1.y * p2.x 所以代码就好写了。 代码：
#include
double x, y;
point(double x1, double y1) {
x = x1; y = y1; } }; class line { public: point n;
line(point & p1, point &p2): n(p2.x - p1.x, p2.y - p1.y){} friend double X(line & l1, line & l2);//叉乘 };
double X(line & l1, line & l2)//叉乘 {
return l1.n.x * l2.n.y - l1.n.y * l2.n.x; }
inline double min(double a, double b) {
if(a < b) return a; else
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库acm算法经典例题(4)在线全文阅读。
相关推荐：