Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

网上找到的代码,为什么这也能过,试试数据9 8和9 9

Posted by WeikaiZeng at 2012-08-02 11:01:31 on Problem 2773 and last updated at 2012-08-02 11:03:55
#include <iostream>
#include <cstdio>
#include<cstring>
using namespace std;

int eular(int n) {
    int sum = 1;
    for (int i = 2; i * i < n; i++) {
        if (n % i == 0) {
            n /= i, sum *= i - 1;
            while (n % i == 0)
                sum *= i, n /= i;
        }
    }
    if (n > 1) sum *= n - 1;
    return sum;
}

int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b, a = b, b = c;
    }
    return a;
}

int main(int argc, char** argv) {
    int m, k, n, i, eul;
    while (scanf("%d%d", &m, &k) != -1) {
        eul = eular(m);
        n = k / eul;
        k %= eul;
        if (k % eul == 0) {
            n--;
            k = eul;
        }
        for (i = 1; k && i <= m; i++)
            if (gcd(m, i) == 1)
                k--;
        printf("%d\n", i + n * m - 1);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator