Do It Wrong, Get It Right

Do It Wrong, Get It Right Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB Total submit users: 7, Accepted users: 6 Problem 12627 : No special judgement Problem description In elementary school, students learn to subtract fractions by first getting a common denominator and then subtracting the numerators. However, sometimes a student will work the problem incorrectly and still arrive at the correct answer. For example, for the problem 5 9 4 12

one can subtract the numbers in the numerator and then subtract the numbers in the denominator, simplify and get the answer. i.e.

For a given fraction b/n, your task is to find all of the values a and m, where a ≥ 0 and m > 0, for which

Input There will be several test cases in the input. Each test case will consist of a single line with two integers, b and n (1 ≤ b,n ≤ 106) separated by a single space. The input will end with a line with two 0s.

Output For each case, output all of the requested fractions on a single line, sorted from smallest to largest. For equivalent fractions, print the one with the smaller numerator first. Output each fraction in the form “a/m” with no spaces immediately before or after the “/”. Output a single space between fractions. Output no extra spaces, and do not separate answers with blank lines.

Sample Input

9 12 12 14 4 12 0 0

Sample Output

0/24 ⁵⁄₂₀ ⁸⁄₁₆ ⁸⁄₈ ⁵⁄₄ 0/28 ⁹⁄₂₁ ⁹⁄₇ 0/24 ³⁄₁₈ ³⁄₆

Problem Source ACM ICPC Southeast USA Regional Programming Contest 2012

可以枚举m或者a，如果枚举a，计算m涉及到开方操作，所以比较慢，会超时；所以只能枚举m，从2*n枚举到1就可以了。

long long输入输出要用%I64d！一直用的是%lld，纠结了好久啊！！！！

#include <cstdio>
#include <cmath>
#include <cstdlib>
#define LL long long
int main(void)
{
  LL b, n;
  freopen("in.txt", "r", stdin);
    while (~scanf("%I64d%I64d", &b, &n))
//    while (~scanf("%lld%lld", &b, &n))
    {
        if (b+n==0) break;
        printf("0/%lld", 2*n);
        for(LL m=2*n - 1;m>0;m--) {
            if(m!=n&&(m*b*(2*n-m))%(n*n)==0)
              printf(" %I64d/%I64d",(m*b*(2*n-m))/(n*n),m);
        }
        printf("\n");
    }
  return 0;
}

嗨，中村。