首页 > ACM题库 > HDU-杭电 > hdu 2534 Score-数论应用-[解题报告]C++
2014
02-09

hdu 2534 Score-数论应用-[解题报告]C++

Score

问题描述 :

大家都知道,pfz是“成电杰出学生”,在成电杰出学生的颁奖典礼上,lxh和pfz都没有听台上在说什么,而是在下面讨论当晚的美式足球比赛,lxh预测说纽约巨人队今晚将会得到11分,pfz马上说不可能。因为通常来说美式足球比赛的得分只有3分和7分两种形式,无论怎么得分都不可能得到11分。想了一会以后,lxh发现其实11分以上的分数都是可以得到,于是11就是最大的不可以得到的分数。现在问题来了,如果比赛的得分只有x分和y分两种形式,那么最大的不可以得到的分数是多少呢?

输入:

本题包括多组输入
每组输入2个整数x, y(2<=x, y<=10^8),x=y=0表示输入结束

输出:

本题包括多组输入
每组输入2个整数x, y(2<=x, y<=10^8),x=y=0表示输入结束

样例输入:

3 7
2 2
0 0

样例输出:

11
Inf

http://acm.hdu.edu.cn/showproblem.php?pid=2534

由题知,

每一个数据都可以由ax +by组成;

ax1 + by1 – c x2 a – d y2 == 1 ;

ans = a * b – a – b ;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<iomanip>

using namespace std;

__int64 gcd( __int64 a , __int64 b )
{
	return b == 0 ? a : gcd( b , a % b ) ;
}
int main()
{
	__int64 n , m ;
	while( scanf( "%I64d%I64d" ,&n ,&m ) , n | m )
	{
		if( gcd( n , m ) == 1 )
			printf( "%I64d\n" , n * m - n - m ) ;
		else
			printf( "Inf\n" ) ;
	}
	return 0 ;
}

解题转自:http://blog.csdn.net/bo_jwolf/article/details/9374251


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。