A－Rudy的礼物
Time Limit: 2000/1000 MS (Java/Others)   Memory Limit: 65536/32768 K (Java/Others)
Description
      过几天Rudy要过生日了，于是Rudy的好G友(Google+好友~)CydorniaKnight穿越回HFUT，给Rudy带了份生日礼物，当然CydoriaKnight的礼物当然不是就那么轻易可以拿到的，礼物装在一个盒子里面，盒子上有把密码锁，同时盒子上有两个正整数n和p，保证p是素数并且n < p， 打开密码锁的密码是一个正整数m，m必须满足这么两个条件：
       1.n * m = 1 (mod p)
       2.m < p
       现在就请HFUT ACMer们帮Rudy把这个问题解决了吧，当然p的值可能会非常大，所以小盆友们就不要尝试用蛮力方法了～

Input
       输入数据有多行，每行有两个正整数n和p，p是素数，同时0 < n < p < 100000008。输出以文件终止符结束。

Output
      输出占一行，每行有一个整数m，保证所有的结果都存在且仅存在唯一的m。

Sample Input
8 11
4 7
3 29
8 100000007

Sample Output
7
2
10
12500001

Hint
      据说装在盒子里的礼物是个很有爱的XX娃娃～

合工大8月1日下午赛试题啊，跪求解答

#include <stdio.h>

int get_m(int n, int p, int sign) {
    if (n == 1) {
        return 1;
    } else {
        if ((p + sign) % n == 0) {
            return (p + sign) / n;
        } else {
            int k = get_m(p % n, n, -sign);
            return (p / n) * k + ((p % n) * k + 1) / n;
        }
    }    
}

int main(int argc, char* argv[]) {
    int n, p, i;
    for (i = 0; i < 4; i++) {
        scanf("%d %d", &n, &p);
        printf("%d\n", get_m(n, p, 1));
    }
    return 0;
}

[ 本帖最后由 voidx 于 2011-8-6 17:43 编辑 ]

上面的算法用了一点点 modular arithmetic 的知识。

ps: main 函数只是为了测试方便而写的

怎么没有回应~

printf("%d\n", get_m(n, p, 1));    // 如果输出换行的话，就不需要fflush了。

俺用的 mintty ，所以加上了，删掉也不影响