将代码贴出来请人帮忙实在是实在是没办法了哦....
我自己测试数据一个也没有出错过啊....却 WA 了不知多少次了!
我连运算结果都进行测试了, 应该没什么问题啊.
可能出问题的就该是 miller-rabin 了. 但是我都开到  32  次测试了.
希望哪位兄台可以帮忙看看, 3x ~~~~



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

typedef long long lltype;

const int MAX_COUNT = 32;
lltype fMyRand();
//back = (a*b)%num
lltype fMultiModular(const lltype &a, lltype b, const lltype &n);
//miller-rabin法测试素数, count 测试次数
bool miller_rabin(const lltype &n, int count);
// d == a^b(mod n) 
lltype modular_exp(const lltype &a, lltype b, const lltype &n);
//a and b can be any integer in [-2147483647, 2147483647]
lltype fGCD(const lltype &a, const lltype &b);

//allFactor[0] 记录了 factor number 
void fFindFactor(const lltype &num, lltype *allFactor);
lltype pollard_rho(const lltype &c, const lltype &num);

int main()
{
    //printf("%I64d\n", fMultiModular(123, 235, 23));
    srand( 215348768 );
    int nCase, i;
    lltype num, minAns, allFactor[64];
    for (scanf("%d", &nCase); nCase > 0; --nCase)
    {
        scanf("%I64d", &num);
        if ( miller_rabin(num, MAX_COUNT) == true )
        {
            for (int t = 1; t <= 10; ++t)
                if ( miller_rabin(num, MAX_COUNT) == false )
                    t /= t-t;
            printf("Prime\n");
        }
        else
        {
            //for ( ; ; );
            *allFactor = 0;
            fFindFactor(num, allFactor);
            minAns = num + 1;
            lltype test(1);
            if  ( *allFactor >= 63 )
                for ( ;  ; );
            //for (i = *allFactor; i > 0; --i)
            for (i = 1; i <= *allFactor; ++i)
            {
                if ( allFactor[i] < minAns )
                    minAns = allFactor[i];
                if ( miller_rabin(allFactor[i], MAX_COUNT) == false )
                    i /= i - i;
                test *= allFactor[i];
            }
            if ( minAns <= 1 || minAns >= num || test != num )
                //test /= test-test;
                for ( ; ; ) ;
            printf("%I64d\n", minAns);
        }        
    }
    //scanf("%#");
	return 0;
}

lltype fMyRand()
{
    lltype result = 0;
    for (int i = 0; i <= 61; ++i)
        if ( (rand()) & 0x1 )
            result += 1LL<<i;
    return result;
}

lltype pollard_rho(const lltype &c, const lltype &num)
{
    //srand( rand()%100000000 + 21423547 );
    int i(1), k(2);
    //lltype x = rand() % num;
    lltype x = fMyRand() % num;
    lltype y = x, comDiv;
    do
    {
        ++i;
        x = (fMultiModular(x, x, num) + num - c + num) % num;
        if ( x == y )
            break;
        comDiv = fGCD((y-x+num+num)%num, num);
        if ( comDiv > 1 && comDiv < num )
            return comDiv;
        if ( i == k )
        {
            y = x;
            k <<= 1;
        }
    }while ( true );
    return num;
}

void fFindFactor(const lltype &num, lltype *allFactor)
{
    if ( miller_rabin(num, MAX_COUNT) == true )
    {
        allFactor[++(*allFactor)] = num;
        return;
    }
    lltype factor;
    do
    {
        //factor = pollard_rho(rand()%(num-1) + 1, num);
        factor = pollard_rho(fMyRand()%(num-1) + 1, num);
        //factor = pollard_rho(1, num);
    }while ( factor >= num );
    fFindFactor(factor, allFactor);
    fFindFactor(num/factor, allFactor);
}

//back = (a*b)%num      ( n <= 2^62)
lltype fMultiModular(const lltype &a, lltype b, const lltype &n)
{
    if ( n <= 0 )
        //throw ( -44 );
        for ( ;  ; ) ;
    lltype back(0), temp(a % n);
    b %= n;
    while ( b > 0 )
    {
        if ( b & 0x1 )
            back = (back + temp) % n;
        temp = (temp<<1) % n;
        b >>= 1; 
    }
    return back;
}

// d == a^b(mod n) 
lltype modular_exp(const lltype &a, lltype b, const lltype &n)
{
    lltype d(1), dTemp(a % n);		        //当前二进制位表示的是进制数值
    while ( b > 0 )
    {
        if ( b & 0x1 )
            d = fMultiModular(d, dTemp, n);
        dTemp = fMultiModular(dTemp, dTemp, n);		//这里需要注意一些问题, 如果 n 很大, 可能会超出范围!!!!
        b >>= 1;
    }
    return d;
}

//miller-rabin法测试素数, count 测试次数
bool miller_rabin(const lltype &n, int count) 
{
    srand( rand() % 1000000 + 2431757 );
    if ( n == 1 )
        return false;       //n should be >= 1 below
    lltype a;		//为了谨慎起见用了 lltype, 而没有用 int
    for (int i = 1; i <= count; ++i)
    {
        //a = rand() % (n-1) + 1;
        a = fMyRand() % (n-1) + 1;
        //a = (i+12536489) % (n-2) + 2;
        if ( modular_exp(a, n-1, n) != 1 )
            return false;
    }
    return true;
}

//a and b can be any integer in [-2147483647, 2147483647]
lltype fGCD(const lltype &a, const lltype &b)
{
	return b == 0 ? a : fGCD(b, a%b);
}

/*
10
18014398509481987
9007199254740993
55
128
125
18014398509481987
9007199254740993
149
2
3
5
10
*/

• Re:请问我为什么 WA 了？ ---- 万分感谢！ (15) henry441120 2006-10-05 22:33:58