HDU5584 证明题..

115 阅读 0 评论 76 点赞

我是靠谱客的博主热心啤酒，最近开发中收集的这篇文章主要介绍HDU5584 证明题..，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
A frog has just learned some number theory, and can’t wait to show his ability to his girlfriend.

Now the frog is sitting on a grid map of infinite rows and columns. Rows are numbered 1, 2, cdots from the bottom, so are the columns. At first the frog is sitting at grid (s_x, s_y), and begins his journey.

To show his girlfriend his talents in math, he uses a special way of jump. If currently the frog is at the grid (x, y), first of all, he will find the minimum z that can be divided by both x and y, and jump exactly z steps to the up, or to the right. So the next possible grid will be (x + z, y), or (x, y + z).

After a finite number of steps (perhaps zero), he finally finishes at grid (e_x, e_y). However, he is too tired and he forgets the position of his starting grid!

It will be too stupid to check each grid one by one, so please tell the frog the number of possible starting grids that can reach (e_x, e_y)!
Input
First line contains an integer T, which indicates the number of test cases.

Every test case contains two integers e_x and e_y, which is the destination grid.

cdot 1 leq T leq 1000.
cdot 1 leq e_x, e_y leq 10^9.
Output
For every test case, you should output ” Case #x: y”, where x indicates the case number and counts from 1 and y is the number of possible starting grids.
Sample Input
3
6 10
6 8
2 8
Sample Output
Case #1: 1
Case #2: 2
Case #3: 3

这个题首先想到的是几变几的问题…
首先给你两个数，按照他那样的转移看上去似乎有两个结果
但是实际上用脑子想想
就能想到小的那个之前肯定是有
大的那个是LCM+另一个
所以应该是一种前提只能转移出一种情况
然后…
GCD我就求不出来了…
死也求不出来
彩笔本质暴露了…
百度了题解…………………………………………………….
发现设x,y为m1k,m2k，他们的转移应该是m1k+m1*m2k,m2k
然后提公因式….
m2m1互质m2 m2+1互质后面这个是对所有自然数成立的记好….
就发现所有的gcd都是k..
哎我的数学素养还差的远呢根本发现不了玛德…

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
long long
gcd(long long
a, long long
b)
{
if (b == 0) return a;
return gcd(b, a%b);
}
int main()
{
int T;
cin >> T;
int u = 0;
long long n, m;
while (T--)
{
scanf("%lld%lld", &n, &m);
if (n < m)
{
long long uu = n;
n = m;
m = uu;
}
long long gcdd = gcd(n, m);
long long
jishu = 1;
while ((n) % (gcdd + m) == 0)
{
n = (n*gcdd) / (gcdd + m);
jishu++;
if (n < m)
{
long long uu = n;
n = m;
m = uu;
}
}
printf("Case #%d: %lldn", ++u, jishu);
}
return 0;
}