HDU5584 LCM Walk 数论 LCM Walk

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 47 Accepted Submission(s): 31

Problem 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

Input

First line contains an integer

Output

For every test case, you should output "Case #x: y", where

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

Source

2015ACM/ICPC亚洲区上海站-重现赛（感谢华东理工）

2015acm上海区域赛的第三道水题。。第一开始以为是推公式然后o（1）求出答案，然而貌似并不能，最后还是想了个暴力枚举公因子吧。。

容易得知，x,y里面肯定是较小的数不变，较大的那个数是从之前某个数变化来的，假设x>y，（x,y）是从（x1，y）变化来的，那么：

x = x1 + x1*y/gcd(x1,y)；则x1 = x/（1 + y/gcd（x1,y））；

那么就很好说了，枚举gcd（x1,y），即枚举y的因子，反求出x1,然后判断x1是否合理，合理的话就继续递归（x1,y），这里枚举因子有一个细节需要

注意，就是对于y是完全平方数的时候，枚举上界是sqrt（y-0.5），然后对于x = sqrt（y）的情况特判，因为忘了注意这点此贡献了一次WA。。

为什么要这样子呢。。因为O（根号n)枚举因子时，如果i是y的因子，那么y/i也是y的因子，这里要判断两个因子，但是i*i=y时，必须只判断一次

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

int t;
int x,y;
int ans;

int gcd(int x, int y)
{
    return x == 0?y : gcd(y%x,x);
}

void dfs(int x, int y)
{
    ans++;
    if(x < y) swap(x,y);
    int p = sqrt(y - 0.5);
    int i;
    for(i = 1; i <= p; ++i)
    {
        if(y % i == 0)
        {
            if(x%(1+y/i) == 0&&gcd(x/(1+y/i),y) == i) dfs(x/(1+y/i),y);
            if(x%(1+i) == 0&&gcd(x/(1+i),y) == y/i) dfs(x/(1+i),y);
        }
    }
    if(i*i == y)
    {
        if(x%(1+i) == 0&&gcd(x/(1+i),y) == i) dfs(x/(1+i),y);
    }
}

int main()
{
    int cas = 1;
    for(cin >> t; cas <= t; ++cas)
    {
        ans = 0;
        scanf("%d%d",&x,&y);
        dfs(x,y);
        printf("Case #%d: %d
",cas,ans);
    }    
}

HDU5584 LCM Walk 数论 LCM Walk

相关推荐