给定两个正整数m和n（m,n>1），求最小的正整数d，满足如下要求（n^d表示n的d次方）
       (n^d-1)能够被(m*n-1)整除


输入样例
2 2
12 11
22 20
32 20
42 38
9952 6231
9962 7277
9972 8898
9982 9508
9992 9320
0 0


输出样例
2
65
219
42
140
6201091
619602
2802024
103740
276660


提示
提示，在[1,m*n-2]范围内一定能找到满足条件的答案

好像d是在φ(n*m-1)的因子里，但不会求最小值

穷举法，从1开始一个一个试，用FOR循环很容易，满足题设条件跳出循环

#include <stdio.h>

int main(void)
{
    int m, n;
    int t;
    printf("请输入大于1的 m n : ");
    scanf("%d %d", &m, &n);
    m = m*n - 1;
    if ((n - 1) % m == 0)
        printf("d = 1\n");
    else
        for (int d = 2, t = n;; d++)
        {
            t *= n;
            printf("d = %d 时 n^d-1 = %d , m = %d , (n^%d-1) %% m = %d\n", d, t - 1, m, d, t % m);
            if ((t - 1) % m == 0)
            {
                printf("d = %d\n", d);
                break;
            }
        }

    return 0;
}

题目是错的，即使我用long long型也算不出

很明显不能用一般方法咯~要取余数接着算~而不是拿那个大数据算~

玩惯脑筋急转弯就不难了~用long long 应该可以~

#include <stdio.h>

int main(void)
{
    int m=0;
    int n=0;

    int t=0;

    int i=0;

    printf("请输入m n:");

    scanf("%d%d",&m,&n);

    for (i=1,t=n;n!=1;++i)
    {
        n*=t;
        n%=(m*t-1);
    }

    printf("%d\n",i);

    return 0;
}

[此贴子已经被作者于2017-3-6 22:35编辑过]

关键点：不是大数运算就是规避大数运算！
等着有人基于整个出答案~~

要规避大数运算的话可以考虑把乘法当作加法分开一步一步算~超出m*n-1则取其余数继续算~

在这个基础上关键是要找到一条余数迭代式--即用上一个余数直接推导出下一个余数而避开两个大数相乘~

当然如果能找到数学公式就有可能一步到位了~不过这只是个猜想而已~

感觉题目m*n-2~应该在int范围内~

数学公式还是首要考虑目标，可惜算法不精，不清楚有没有相关

感觉可以用double保存数据或者用double百分比来算出余数迭代式~