试试这个~不过vc好像不支持unsigned long long int 型~试试用.cpp~~

#include<stdio.h>

int fun(int m, int n);

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

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

    while (s=fun(m,n))
    {
        printf("%d\n",s);
        scanf("%d%d",&m,&n);
    }

    return 0;
}

int fun(int m,int n)
{
    unsigned long long  int a=0;
    
    int t=0;

    int i=0;

    if (m==0||n==0)
        return 0;

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

    return i;
}

PS:如果这样就过了的话那九九就无语了~如果还是超时~这题就交给数学老师处理算啦~

PPS:如果真的要用到long long 型~九九猜这应该不是正规的AC题~很可能是学校自己编的~数据弄得这么大~感觉不太地道~而且正规的AC题应该是给出m n的最大取值范围的~如果真的有AC代码~九九倒要看看那AC的数学公式是怎么样的~是不是在考高数~~~~~~~~~~

PPPS:有没有原题的出处或者包括网址~看看能不能发一下~如果不方便参考就算了~

[此贴子已经被作者于2017-3-8 23:11编辑过]

正解。

遍历φ(n*m-1)的因子，用快速幂算出mod值。

φ(n*m-1)里的因子是和n*m-1互质的，求互质数集合也很麻烦啊。个人感觉分两步：
1，先求指数d的最小起点：d=log(n*m-1)/log(n);
2,d到n*m-1循环，直到((n^d*d)%(n*m-1)-n*m-1)%(n*m-1)==0，由于每次循环数据都不大于（n*m-1）,这样不用担心数据太大溢出。

每次迭代新的余数不同~就是说每次迭代新的余数不会重复~不然就会陷入死循环了~感觉这条题目要注意两个问题~一个是数据溢出~另一个是超时问题~

[此贴子已经被作者于2017-3-9 15:19编辑过]

修正23楼错误：1%x=1,所以k=(k*n)%j,判断k==1即可，以下代码在vc6下题主给出的实例均验证正确，不知道超时不：

#include <stdio.h>
int main()
{
    unsigned int i,n,m;
    unsigned _int64 j,k;
    while(scanf("%d%d",&n,&m)&&(n|m))
    {
        j=n*m-1;
        for(i=1,k=n;i<j&&k!=1;i++)
            k=(k*n)%j;
        if(i<j)printf("%d\n",i);
    }
    return 0;
}

unsigned _int64 j,k;

这个九九见得不多~要学习一下了~

在gcc、g++编译器里就是unsigned long long j,k;我测试了下：在我电脑上，得到题主提供的范例最大的得数为6201091时，用时125毫秒，应该不超时的。

[此贴子已经被作者于2017-3-9 15:27编辑过]

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

#define  MAX  10001

int fac[1024], facCount;
bool isPrime[MAX] = {false};
int primeFactor[10][2], primeFacCount;
int phi[MAX], prime[MAX], priCount = 0;

/*

 * MAX 内数据初始化

 */
void initialize()
{
    phi[1] = 1;
    for (int i = 2; i < MAX; ++i)
    {
        if (!isPrime[i])
        {
            prime[priCount++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < priCount; ++j)
        {
            if (i * prime[j] >= MAX) break;

            isPrime[i * prime[j]] = true;

            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            else
            {
                phi[i * prime[j]] = (prime[j] - 1) * phi[i];
            }
        }
    }
}

/*

 * 获取phi

 */
int getPhi(int n)
{
    if (n < MAX) return phi[n];

    int pos = 0, result = 1;
    while (pos < priCount && n >= MAX)
    {
        while (0 == n % prime[pos])
        {
            n /= prime[pos], result *= phi[prime[pos]];
        }
        pos += 1;
    }
    return pos < priCount ? result * phi[n] : result * (n - 1);
}

/*

 * 快速模

 */
long long quickMode(long long a, long long b, long long n)
{
    long long ret = 1;
    for (; b; b /= 2)
    {
        if (b & 1) ret = ret * a % n;
        a = a * a % n;
    }
    return ret;
}

/*

 * 所有因数

 */
void allFactor(int pos, int result)
{
    if (pos >= primeFacCount)
    {
        fac[facCount++] = result;
        return;
    }

    allFactor(pos + 1, result);
    for (int i = 0; i < primeFactor[pos][1]; ++i)
    {
        result *= primeFactor[pos][0];
        allFactor(pos + 1, result);
    }
}

/*

 * 所有质因数

 */
void initPrimeFactor(int n)
{
    int pos = 0;
    primeFacCount = 0;
    while (pos < priCount && n > 1)
    {
        if (0 == n % prime[pos])
        {
            primeFactor[primeFacCount][0] = prime[pos], primeFactor[primeFacCount][1] = 0;
            while (0 == n % prime[pos])
            {
                n /= prime[pos], primeFactor[primeFacCount][1] += 1;
            }
            primeFacCount++;
        }
        pos += 1;
    }
    if (pos >= priCount) primeFactor[primeFacCount][0] = n, primeFactor[primeFacCount++][1] = 1;
}

/*

 * 快排传入函数

 */
int cmp(const void *a, const void *b) { return *(int *) a - *(int *) b; }

int main()
{
    initialize();

    int i, m, n;

    freopen("../stdin", "r", stdin);
    while (2 == scanf("%d%d", &m, &n) && n > 1)
    {
        clock_t beg = clock();
        int p = n * m - 1, q = getPhi(p);
//        printf("φ(%d) = %d = ", p, q);

        initPrimeFactor(q);
//        for (i = 0; i < primeFacCount; ++i)
//        {
//            if (i) printf(" * ");
//            printf("%d", primeFactor[i][0]);
//            if (primeFactor[i][1] > 1) printf(" ^ %d", primeFactor[i][1]);
//        }
//        printf("\n");

        facCount = 0, allFactor(0, 1);

        qsort(fac, facCount, sizeof(fac[0]), cmp);

//        for (i = 0; i < facCount; ++i) printf("%d%c", fac[i], "\n "[i < facCount - 1]);

        for (i = 0; i < facCount; ++i)
        {
            if (1 == quickMode(n, fac[i], p)) break;
        }
        printf("%d\n", fac[i]);
        printf("all runs %lf seconds\n", (double) (clock() - beg) / CLOCKS_PER_SEC);
    }

    return 0;
}

[此贴子已经被作者于2017-3-9 17:58编辑过]

a^n mod b = 1

a^(kn) mod b = (a^n *...* a^n) mod b = (a^n mod b) *...* (a^n mod b) = 1

所以部分因数不用处理的

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define  MAX  10001

int fac[10][2], facCount;
bool isPrime[MAX] = {false};
int phi[MAX], prime[MAX], priCount = 0;

/*

 * MAX 内数据初始化

 */
void initialize()
{
    phi[1] = 1;
    for (int i = 2; i < MAX; ++i)
    {
        if (!isPrime[i])
        {
            prime[priCount++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < priCount; ++j)
        {
            if (i * prime[j] >= MAX) break;

            isPrime[i * prime[j]] = true;

            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            else
            {
                phi[i * prime[j]] = (prime[j] - 1) * phi[i];
            }
        }
    }
}

/*

 * 获取phi

 */
int getPhi(int n)
{
    if (n < MAX) return phi[n];

    int pos = 0, result = 1;
    while (pos < priCount && n >= MAX)
    {
        while (0 == n % prime[pos])
        {
            n /= prime[pos], result *= phi[prime[pos]];
        }
        pos += 1;
    }
    return pos < priCount ? result * phi[n] : result * (n - 1);
}

/*

 * 快速模

 */
long long quickMode(long long a, long long b, long long n)
{
    long long ret = 1;
    for (; b; b /= 2)
    {
        if (b & 1) ret = ret * a % n;
        a = a * a % n;
    }
    return ret;
}

/*

 * 所有质因数

 */
void factor(int n)
{
    int pos = 0;
    facCount = 0;
    while (pos < priCount && n > 1)
    {
        if (0 == n % prime[pos])
        {
            fac[facCount][0] = prime[pos], fac[facCount][1] = 0;
            while (0 == n % prime[pos])
            {
                n /= prime[pos], fac[facCount][1] += 1;
            }
            facCount++;
        }
        pos += 1;
    }
    if (pos >= priCount) fac[facCount][0] = n, fac[facCount++][1] = 1;
}

int main()
{
    initialize();

    int i, m, n;

    freopen("../stdin", "r", stdin);
    while (2 == scanf("%d%d", &m, &n) && n > 1)
    {
        clock_t beg = clock();
        int p = n * m - 1, q = getPhi(p);
//        printf("φ(%d) = %d = ", p, q);

        factor(q);
//        for (i = 0; i < facCount; ++i)
//        {
//            if (i) printf(" * ");
//            printf("%d", fac[i][0]);
//            if (fac[i][1] > 1) printf(" ^ %d", fac[i][1]);
//        }
//        printf("\n");

        int ans = q;
        for (i = 0; i < facCount; ++i)
        {
            while (fac[i][1] && 1 == quickMode(n, ans / fac[i][0], p))
            {
                ans /= fac[i][0], fac[i][1] -= 1;
            }
        }

        printf("%d\n", ans);
        printf("all runs %lf seconds\n", (double) (clock() - beg) / CLOCKS_PER_SEC);
    }

    return 0;
}

不好意思  回复的晚了；
题目要求是一秒
n,m没有给数据范围--