──── inkfish (Fri Sep  3 12:01:40 2004)   ────────────


【 在 kinfkong (  此ID已killed  ) 的大作中提到: 】
: 1. 计算星期几的公式：
:   是不是这样子啊：((13*M-1)/5+D+Y/4+Y+C/4-2*C)%7
:   忘了在哪里抄来的，试了试，怎么不行的？
《初等数论》后面附录有

: 2. 如果用Rabbin的素数速试，如何避过Carmicheal number
:   的干扰? 
: thx


──── iamcs (Fri Sep  3 12:37:30 2004)   ─────────────


【 在 kinfkong (  此ID已killed  ) 的大作中提到: 】
: 1. 计算星期几的公式：
:   是不是这样子啊：((13*M-1)/5+D+Y/4+Y+C/4-2*C)%7
:   忘了在哪里抄来的，试了试，怎么不行的？
 2. 如果用Rabbin的素数速试，如何避过Carmicheal number
   的干扰? 
  
   把那些数记下来，反正很少。
: thx


──── iamcs (Fri Sep  3 12:52:52 2004)   ─────────────

这几个 
561,41041,825265,321197185

【 在 kinfkong (  此ID已killed  ) 的大作中提到: 】
:  给我一个list，我google到的都是比较小的。
: 【 在 iamcs (Savior) 的大作中提到: 】
: :  2. 如果用Rabbin的素数速试，如何避过Carmicheal number
: :    的干扰? 
: :    把那些数记下来，反正很少。


──── iamcs (Mon Sep  6 21:03:32 2004)   ─────────────

谁贴个Rabbin-Miller和 Pollard分解的代码吧

【 在 kinfkong (  此ID已killed  ) 的大作中提到: 】
: 1. 计算星期几的公式：
:   是不是这样子啊：((13*M-1)/5+D+Y/4+Y+C/4-2*C)%7
:   忘了在哪里抄来的，试了试，怎么不行的？
: 2. 如果用Rabbin的素数速试，如何避过Carmicheal number
:   的干扰? 
: thx


──── magicpig (Mon Sep  6 22:04:21 2004)  ────────────

我贴一个吧，请指教。
（以下程序只能平方不超过__int64的情况下应用，对大数据要定义大数运算）
                  -----------输入的n，满足n*n<=2^63
//////////////////////////////////////////////////////
#define MAX 100
__int64 random(){
        __int64 a;
        a = rand();
        a *= rand();
        a *= rand();
        return a;
}
//////////////////////////////////////////////////////
//Miller_Rabin
__int64 square_multiply(__int64 x, __int64 c, __int64 n){
        __int64 z;
        z = 1;
        while(c){
                if(c%2==1)z = (z*x)%n;
                x = (x*x)%n;
                c=(c>>1);
        }
        return z;
}
bool Miller_Rabin(__int64 n){
        __int64 k = 0, i, j, m, a;
        m = n - 1;
        while(m%2==0)m=(m>>1),k++;
        for(i=0;i<MAX;i++){
                a = 0;
                while(a==0)a  = random()%n;
                a = square_multiply(a, m, n);//平方乘
                if(a==1)continue;
                for(j=0;j<k;j++){
                        if(a==n-1)break;
                        a = (a*a)%n;
                }
                if(j<k)continue;
                return false ;
        }
        return true;
}
/////////////////////////////////////////////////////////
//Pollard p,只找出一个因子。
__int64 gcd(__int64 a,__int64 b){
        if(a%b==0)return b;
        else return gcd(b,a%b);
}
//用公式f(x) = x^2 + 1检验碰撞。
__int64 f(__int64 x){
        return x*x+1;
}
__int64 Pollard(__int64 n){
        __int64 i,  p, x,xx;
        for(i=1;i<MAX;i++){
                x = i;
                xx = f(x)%n;
                p = gcd((xx-x+n)%n,n);
                while(p==1){
                        x = f(x)%n;
                        xx = f( f(xx)%n )%n;
                        p = gcd( (xx-x+n)%n,n)%n;
                }
                if(p==0)continue ;
                else return p;
        }
        return -1;
}

【 在 iamcs (Savior) 的大作中提到: 】
: 谁贴个Rabbin-Miller和 Pollard分解的代码吧
: 【 在 kinfkong (  此ID已killed  ) 的大作中提到: 】
: : 1. 计算星期几的公式：
: :   是不是这样子啊：((13*M-1)/5+D+Y/4+Y+C/4-2*C)%7
: :   忘了在哪里抄来的，试了试，怎么不行的？
: : 2. 如果用Rabbin的素数速试，如何避过Carmicheal number
: :   的干扰? 
: : thx


──── magicpig (Mon Sep  6 22:06:09 2004)  ────────────

补充一个主函数，完整代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
__int64 random(){
        __int64 a;
        a = rand();
        a *= rand();
        a *= rand();
        return a;
}
//////////////////////////////////////////////////////
//Miller_Rabin
__int64 square_multiply(__int64 x, __int64 c, __int64 n){
        __int64 z;
        z = 1;
        while(c){
                if(c%2==1)z = (z*x)%n;
                x = (x*x)%n;
                c=(c>>1);
        }
        return z;
}
bool Miller_Rabin(__int64 n){
        __int64 k = 0, i, j, m, a;
        m = n - 1;
        while(m%2==0)m=(m>>1),k++;
        for(i=0;i<MAX;i++){
                a = 0;
                while(a==0)a  = random()%n;
                a = square_multiply(a, m, n);//平方乘
                if(a==1)continue;
                for(j=0;j<k;j++){
                        if(a==n-1)break;
                        a = (a*a)%n;
                }
                if(j<k)continue;
                return false ;
        }
        return true;
}
/////////////////////////////////////////////////////////
//Pollard p,只找出一个因子。
__int64 gcd(__int64 a,__int64 b){
        if(a%b==0)return b;
        else return gcd(b,a%b);
}
//用公式f(x) = x^2 + 1检验碰撞。
__int64 f(__int64 x){
        return x*x+1;
}
__int64 Pollard(__int64 n){
        __int64 i, p, x,xx;
        for(i=1;i<MAX;i++){
                x = i;
                xx = f(x)%n;
                p = gcd((xx-x+n)%n,n);
                while(p==1){
                        x = f(x)%n;
                        xx = f( f(xx)%n )%n;
                        p = gcd( (xx-x+n)%n,n)%n;
                }
                if(p==0)continue ;
                else return p;
        }
        return -1;
}
//////////////////////////////////////////////////
void main(){
        __int64 a;
        while(scanf("%I64d",&a)!=EOF)
                if(Miller_Rabin(a))printf("prime\n");
                else printf("%I64d\n",Pollard(a));
}

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 我贴一个吧，请指教。
: （以下程序只能平方不超过__int64的情况下应用，对大数据要定义大数运算）
: //////////////////////////////////////////////////////
: #define MAX 100
: __int64 random(){
:         __int64 a;
:         a = rand();
:         a *= rand();
:         a *= rand();
:         a *= rand();
: .................（以下省略）


──── magicpig (Mon Sep  6 22:07:22 2004)  ────────────

连分数分解是指？

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  你会不会用连分数来分解？
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 谁贴个Rabbin-Miller和 Pollard分解的代码吧


──── iamcs (Mon Sep  6 22:12:11 2004)   ─────────────

不懂。

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  就是用连分数结合Legendre的方法来分解因子咯
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 连分数分解是指？


──── iamcs (Mon Sep  6 22:12:37 2004)   ─────────────

赞一个！

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 我贴一个吧，请指教。
: （以下程序只能平方不超过__int64的情况下应用，对大数据要定义大数运算）
: //////////////////////////////////////////////////////
: #define MAX 100
: __int64 random(){
:         __int64 a;
:         a = rand();
:         a *= rand();
:         a *= rand();
:         a *= rand();
: .................（以下省略）


──── magicpig (Mon Sep  6 23:25:04 2004)  ────────────

第一次给人赞，很开心啊。
谢谢实哥
【 在 iamcs (Savior) 的大作中提到: 】
: 赞一个！
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 我贴一个吧，请指教。
: : （以下程序只能平方不超过__int64的情况下应用，对大数据要定义大数运算）
: : //////////////////////////////////////////////////////
: : #define MAX 100
: : __int64 random(){
: :         __int64 a;
: :         a = rand();
: :         a *= rand();
: .................（以下省略）


──── dynamic (Mon Sep  6 23:27:03 2004)   ────────────

呵呵，导论上就有的
失败的概率不超过1/4，很安全的

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  终于明白了，原来我以前认识到的Miller-Rabin是如此的naive, 
:  只要改进一下，Carmichael Numbers居然是如此不堪一击.
: 【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
: :  点解你这个程序对Carmichael Numbers都可以成功检出来的？
: :  牛
: : .................（以下省略）


──── infant (Mon Sep  6 23:47:05 2004)  ─────────────

pollard p 算出来的是最小的那个因子吗？
如果要求其他因子是不是n=n/p再用一次?
【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 补充一个主函数，完整代码：
: #include <stdio.h>
: #include <stdlib.h>
: #define MAX 100
: __int64 random(){
:         __int64 a;
:         a = rand();
:         a *= rand();
:         a *= rand();
:         return a;
: .................（以下省略）


──── infant (Mon Sep  6 23:53:50 2004)  ─────────────

好像书上说只要查找2lg^2次证据就行了。那么就是说循环2lg^2就一定保险了，对吗？
【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: 呵呵，导论上就有的
: 失败的概率不超过1/4，很安全的
: 【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
: :  终于明白了，原来我以前认识到的Miller-Rabin是如此的naive, 
: :  只要改进一下，Carmichael Numbers居然是如此不堪一击.


──── magicpig (Mon Sep  6 23:56:15 2004)  ────────────

求其他因子，n=n/p，然后检验其素性再分解
对于pku那题，
我们只要先检验 2到10^6是否有其因子，如果没有
就证明只可能两个大因子，那样子用pollard p找出
一个因子p，再求q ＝ n/p
然后min(p,q)

【 在 infant (infant) 的大作中提到: 】
: pollard p 算出来的是最小的那个因子吗？
: 如果要求其他因子是不是n=n/p再用一次?
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 补充一个主函数，完整代码：
: : #include <stdio.h>
: : #include <stdlib.h>
: : #define MAX 100
: : __int64 random(){
: :         __int64 a;
: :         a = rand();
: .................（以下省略）


──── magicpig (Tue Sep  7 00:00:40 2004)  ────────────

一定？
六合彩也有人中，肯定会有失败的时候。
如果次数足够，失败概率几乎是0，所以安全啊。
对了，2lg^2是什么意思？

【 在 infant (infant) 的大作中提到: 】
: 好像书上说只要查找2lg^2次证据就行了。那么就是说循环2lg^2就一定保险了，对吗？
: 【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: : 呵呵，导论上就有的
: : 失败的概率不超过1/4，很安全的


──── infant (Tue Sep  7 00:05:12 2004)  ─────────────

哦，我懂了。其实可以是2到2^18，这样更省一点，对吧 ^_^
谢谢师兄。^_^
【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 求其他因子，n=n/p，然后检验其素性再分解
: 对于pku那题，
: 我们只要先检验 2到10^6是否有其因子，如果没有
: 就证明只可能两个大因子，那样子用pollard p找出
: 一个因子p，再求q ＝ n/p
: 然后min(p,q)
: 【 在 infant (infant) 的大作中提到: 】
: : pollard p 算出来的是最小的那个因子吗？
: : 如果要求其他因子是不是n=n/p再用一次?
: : .................（以下省略）


──── magicpig (Tue Sep  7 00:07:23 2004)  ────────────

^_^
师弟算的那么准确。

【 在 infant (infant) 的大作中提到: 】
: 哦，我懂了。其实可以是2到2^18，这样更省一点，对吧 ^_^
: 谢谢师兄。^_^
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 求其他因子，n=n/p，然后检验其素性再分解
: : 对于pku那题，
: : 我们只要先检验 2到10^6是否有其因子，如果没有
: : 就证明只可能两个大因子，那样子用pollard p找出
: : 一个因子p，再求q ＝ n/p
: : 然后min(p,q)


──── magicpig (Tue Sep  7 00:08:09 2004)  ────────────

暂时放在你那里，我现在没穿上衣，懒得走来走去。
^_^

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  你下来取回你的书吧 :-)
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 求其他因子，n=n/p，然后检验其素性再分解
: : 对于pku那题，
: : 我们只要先检验 2到10^6是否有其因子，如果没有
: : 就证明只可能两个大因子，那样子用pollard p找出
: : 一个因子p，再求q ＝ n/p
: : 然后min(p,q)


──── infant (Tue Sep  7 00:09:18 2004)  ─────────────

书上说如果n是合数，那么只要查找大小为2lg^2的证据就可以了。所以总的复杂度是
O(lg^5)。
【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 一定？
: 六合彩也有人中，肯定会有失败的时候。
: 如果次数足够，失败概率几乎是0，所以安全啊。
: 对了，2lg^2是什么意思？
: 【 在 infant (infant) 的大作中提到: 】
: : 好像书上说只要查找2lg^2次证据就行了。那么就是说循环2lg^2就一定保险了，对吗？


──── iamcs (Tue Sep  7 00:23:46 2004)   ─────────────

我的更加naive...

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  终于明白了，原来我以前认识到的Miller-Rabin是如此的naive, 
:  只要改进一下，Carmichael Numbers居然是如此不堪一击.
: 【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
: :  点解你这个程序对Carmichael Numbers都可以成功检出来的？
: :  牛
: : .................（以下省略）


──── infant (Tue Sep  7 00:24:55 2004)  ─────────────

哦，对了。师兄我一直搞不懂为什么square_multiply的时间是lg^3。
他做了lg次乘和除，也就是说一次乘和除的时间是lg^2,对吗？
问题可能太弱了，可是我就是想不通。^_^|||
【 在 infant (infant) 的大作中提到: 】
: 书上说如果n是合数，那么只要查找大小为2lg^2的证据就可以了。所以总的复杂度是
: O(lg^5)。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 一定？
: : 六合彩也有人中，肯定会有失败的时候。
: : 如果次数足够，失败概率几乎是0，所以安全啊。
: : 对了，2lg^2是什么意思？


──── magicpig (Tue Sep  7 00:31:32 2004)  ────────────

做一次乘法或取模是lg^2
平方乘要做lg次循环
所以Lg^3

【 在 infant (infant) 的大作中提到: 】
哦，对了。师兄我一直搞不懂为什么square_multiply的时间是lg^3。
他做了lg次乘和除，也就是说一次乘和除的时间是lg^2,对吗？
问题可能太弱了，可是我就是想不通。^_^|||
【 在 infant (infant) 的大作中提到: 】
: 书上说如果n是合数，那么只要查找大小为2lg^2的证据就可以了。所以总的复杂度是
: O(lg^5)。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 一定？
: : 六合彩也有人中，肯定会有失败的时候。
: : 如果次数足够，失败概率几乎是0，所以安全啊。
: : 对了，2lg^2是什么意思？


──── iamcs (Tue Sep  7 00:49:11 2004)   ─────────────

你的Pollard分解中x是循环变量，但是中间又改变了x的值，如果
第一个x的值不成功的话，就会有些怪异。

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 补充一个主函数，完整代码：
: #include <stdio.h>
: #include <stdlib.h>
: #define MAX 100
: __int64 random(){
:         __int64 a;
:         a = rand();
:         a *= rand();
:         a *= rand();
:         return a;
: .................（以下省略）


──── infant (Tue Sep  7 00:51:47 2004)  ─────────────

哦，懂了。我真是个大SB。^_^|||
【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 做一次乘法或取模是lg^2
: 平方乘要做lg次循环
: 所以Lg^3
: 【 在 infant (infant) 的大作中提到: 】
: 哦，对了。师兄我一直搞不懂为什么square_multiply的时间是lg^3。
: 他做了lg次乘和除，也就是说一次乘和除的时间是lg^2,对吗？
: 问题可能太弱了，可是我就是想不通。^_^|||
: 【 在 infant (infant) 的大作中提到: 】
: : 书上说如果n是合数，那么只要查找大小为2lg^2的证据就可以了。所以总的复杂度是
: : O(lg^5)。


──── infant (Tue Sep  7 00:57:18 2004)  ─────────────

好像是波！！ 师兄是不是该加多一个循环变量会好些?
【 在 iamcs (Savior) 的大作中提到: 】
: 你的Pollard分解中x是循环变量，但是中间又改变了x的值，如果
: 第一个x的值不成功的话，就会有些怪异。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 补充一个主函数，完整代码：
: : #include <stdio.h>
: : #include <stdlib.h>
: : #define MAX 100
: : __int64 random(){
: :         __int64 a;
: :         a = rand();
: .................（以下省略）


──── zhonglei (Tue Sep  7 00:59:52 2004)  ────────────


【 在 infant (infant) 的大作中提到: 】
: 好像是波！！ 师兄是不是该加多一个循环变量会好些?
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 你的Pollard分解中x是循环变量，但是中间又改变了x的值，如果
: : 第一个x的值不成功的话，就会有些怪异。
: : .................（以下省略）
大家讨论好热烈啊。。。

──── dynamic (Tue Sep  7 01:00:45 2004)   ────────────

传说你闭关...

【 在 zhonglei (radium) 的大作中提到: 】
: 
: 【 在 infant (infant) 的大作中提到: 】
: : 好像是波！！ 师兄是不是该加多一个循环变量会好些?
: : 【 在 iamcs (Savior) 的大作中提到: 】
: 大家讨论好热烈啊。。。


──── magicpig (Tue Sep  7 01:01:02 2004)  ────────────

不好意思，要改改才行。
^_^

【 在 iamcs (Savior) 的大作中提到: 】
: 你的Pollard分解中x是循环变量，但是中间又改变了x的值，如果
: 第一个x的值不成功的话，就会有些怪异。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 补充一个主函数，完整代码：
: : #include <stdio.h>
: : #include <stdlib.h>
: : #define MAX 100
: : __int64 random(){
: :         __int64 a;
: :         a = rand();
: .................（以下省略）


──── magicpig (Tue Sep  7 01:04:05 2004)  ────────────

谢谢提醒，现在改了。
【 在 iamcs (Savior) 的大作中提到: 】
你的Pollard分解中x是循环变量，但是中间又改变了x的值，如果
第一个x的值不成功的话，就会有些怪异。

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 补充一个主函数，完整代码：
: #include <stdio.h>
: #include <stdlib.h>
: #define MAX 100
: __int64 random(){
:         __int64 a;
:         a = rand();
:         a *= rand();
:         a *= rand();
:         return a;
: .................（以下省略）


──── magicpig (Tue Sep  7 01:06:23 2004)  ────────────

radium出关之日，我们队开始强盛了
【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: 传说你闭关...
: 【 在 zhonglei (radium) 的大作中提到: 】
: : 大家讨论好热烈啊。。。


──── magicpig (Tue Sep  7 01:10:15 2004)  ────────────

^_^
弱啊。
【 在 infant (infant) 的大作中提到: 】
: 呵呵，师兄，好像你这次不比我上次强多少呀 ^_^
: 怎么犯低级错误成了我们队的传统呀！真奇怪。^_^
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 不好意思，要改改才行。
: : ^_^


──── zhonglei (Tue Sep  7 01:33:06 2004)  ────────────


【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: 传说你闭关...
: 【 在 zhonglei (radium) 的大作中提到: 】
: : 
: : 大家讨论好热烈啊。。。
哪里传出来的啊

──── iamcs (Tue Sep  7 08:19:24 2004)   ─────────────

PKU这题有可能中间过程超过in64的范围，怎么办？

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 求其他因子，n=n/p，然后检验其素性再分解
: 对于pku那题，
: 我们只要先检验 2到10^6是否有其因子，如果没有
: 就证明只可能两个大因子，那样子用pollard p找出
: 一个因子p，再求q ＝ n/p
: 然后min(p,q)
: 【 在 infant (infant) 的大作中提到: 】
: : pollard p 算出来的是最小的那个因子吗？
: : 如果要求其他因子是不是n=n/p再用一次?
: : .................（以下省略）


──── magicpig (Tue Sep  7 08:39:51 2004)  ────────────

做一下处理，我是自己定义一个这样的乘法。
a*b的时候不直接乘，把a两位两位乘于b，再取模
因为b最大为2^54,100<2^9=512,所以2^54 * 100<2^63
这样子不会溢出。（可以把100扩大到512）
typedef __int64 pp;
// (a*b)%n
pp by(pp a, pp b, pp n){
        pp t, i, r, j;
        t = i = 0;
        while(a){
                r = (a%100)*b;
                r %= n;
                for(j=0;j<i;j++)r=(r*100)%n;
                t+=r;
                t%=n;
                a/=100;
                i++;
        }
        return t;
}

【 在 iamcs (Savior) 的大作中提到: 】
: PKU这题有可能中间过程超过in64的范围，怎么办？
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 求其他因子，n=n/p，然后检验其素性再分解
: : 对于pku那题，
: : 我们只要先检验 2到10^6是否有其因子，如果没有
: : 就证明只可能两个大因子，那样子用pollard p找出
: : 一个因子p，再求q ＝ n/p
: : 然后min(p,q)


──── iamcs (Tue Sep  7 08:49:48 2004)   ─────────────

555...好麻烦。

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 做一下处理，我是自己定义一个这样的乘法。
: a*b的时候不直接乘，把a两位两位乘于b，再取模
: 因为b最大为2^54,100<2^9=512,所以2^54 * 100<2^63
: 这样子不会溢出。（可以把100扩大到512）
: typedef __int64 pp;
: // (a*b)%n
: pp by(pp a, pp b, pp n){
:         pp t, i, r, j;
:         t = i = 0;
:         while(a){
: .................（以下省略）


──── magicpig (Tue Sep  7 08:54:54 2004)  ────────────

比如
a = 12312
其实可以把a分解 a = 12 + 23*100+ 1*(100)^2
(a*b)%n =
( ( (12*b)%n + (((23*b)%n)*100 )%n )%n  + (((((1*b)%n)*100)%n)*100)%n   )%n
    ------－    ------------------        ---------------------------  
   －－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

这样子做一次乘法取一次模，
而且两个因子的位数保证了不会溢出。

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 做一下处理，我是自己定义一个这样的乘法。
: a*b的时候不直接乘，把a两位两位乘于b，再取模
: 因为b最大为2^54,100<2^9=512,所以2^54 * 100<2^63
: 这样子不会溢出。（可以把100扩大到512）
: typedef __int64 pp;
: // (a*b)%n
: pp by(pp a, pp b, pp n){
:         pp t, i, r, j;
:         t = i = 0;
:         while(a){
: .................（以下省略）


──── magicpig (Tue Sep  7 08:55:46 2004)  ────────────

^_^
我想不到好方法，实哥有什么好的策略吗？

【 在 iamcs (Savior) 的大作中提到: 】
: 555...好麻烦。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : 做一下处理，我是自己定义一个这样的乘法。
: : a*b的时候不直接乘，把a两位两位乘于b，再取模
: : 因为b最大为2^54,100<2^9=512,所以2^54 * 100<2^63
: : 这样子不会溢出。（可以把100扩大到512）
: : typedef __int64 pp;
: : // (a*b)%n
: : pp by(pp a, pp b, pp n){
: :         pp t, i, r, j;
: .................（以下省略）


──── iamcs (Tue Sep  7 08:56:55 2004)   ─────────────

还是这样做比较好。

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: ^_^
: 我想不到好方法，实哥有什么好的策略吗？
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 555...好麻烦。
: : .................（以下省略）


──── iamcs (Tue Sep  7 12:30:59 2004)   ─────────────

受不了！总是WA，完全按照你说的做的，奇怪。

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

typedef long long I64;

int primen;
int prime[25000];

I64 abs(I64 x)
{
  return (x<0)?(-x):x;
}

I64 mod_mul(I64 x,I64 y,I64 n)
{  
  if(!x) return 0;
  return (((x&255)*y)%n+(mod_mul(x>>8,y,n)<<8)%n)%n;
}

I64 myrand()
{
  I64 a=rand();
  a*=rand();
  return abs(a);
}

I64 mod_exp(I64 a,I64 x,I64 n)
{  
  I64 ret=1;
  
  while(x) {
    if(x&1) ret=mod_mul(ret,a,n);
    a=mod_mul(a,a,n);
    x>>=1;
  }
  return ret;
}

I64 gcd(I64 x,I64 y)
{
  I64 q;

  while(1) {
    if(!y) return abs(x);
    q=x,x=y,y=q%y;
  }
}

bool Rabin_Miller(I64 n)
{
  I64 k=0,i,j,m,a;
  
  if(n<2) return 0;
  if(n==2) return 1;
  if(!(n&1)) return 0;
  m=n-1;
  while(!(m&1)) m>>=1,k++;
  for(i=0;i<100;i++) {
    a=myrand()%(n-2)+2;
    a=mod_exp(a,m,n);
    if(a==1) continue;
    for(j=0;j<k;j++) {
      if(a==n-1) break;
      a=mod_mul(a,a,n);
    }
    if(j<k) continue;
    return 0;
  }
  return 1;
}

I64 func(I64 x,I64 n)
{
  return (mod_mul(x,x,n)+1)%n;
}

I64 Pollard(I64 n)
{
  I64 i,x,y,p;

  if(!(n&1)) return 2;
  for(i=1;i<100;i++) {
    x=i;
    y=func(x,n);
    p=gcd(y-x,n);
    while(p==1) {
      x=func(x,n);
      y=func(func(y,n),n);
      p=gcd((y-x+n)%n,n)%n;
    }
    if(p==0 || p==n) continue;
    return p;
  }
  return -1;
}

void init()
{
  const int MAXC=1<<18;
  bool flag[MAXC]={0};
  int i,j,k;

  for(i=2;i*i<MAXC;i++) if(!flag[i])
    for(j=i*i;j<MAXC;j+=i) flag[j]=1;
  primen=0;
  for(i=2;i<MAXC;i++) if(!flag[i]) prime[primen++]=i;  
}

int scan(I64 p)
{
  int i;

  for(i=0;i<primen && prime[i]<=p;i++) 
    if(p%prime[i]==0) return prime[i];
  return -1;
}

int main()
{
  int casen;
  I64 n,p,q;

  srand((unsigned)time(NULL));

  init();
  scanf("%d",&casen);
  while(casen-->0) {
    scanf("%lld",&n);
    if(Rabin_Miller(n)) printf("Prime\n"); else {
      p=scan(n);
      if(p<0) {
        p=Pollard(n);
        q=n/p;
        if(q<p) p=q;
      }
      printf("%lld\n",p);
    }
  }
  return 0;
}

【 在 iamcs (Savior) 的大作中提到: 】
: 还是这样做比较好。
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: : ^_^
: : 我想不到好方法，实哥有什么好的策略吗？


──── infant (Tue Sep  7 12:34:02 2004)  ─────────────

hehe,实哥也有郁闷的时候,罕见丫 ^_^
【 在 iamcs (Savior) 的大作中提到: 】
: 受不了！总是WA，完全按照你说的做的，奇怪。
: #include <stdio.h>
: #include <stdlib.h>
: #include <math.h>
: #include <time.h>
: typedef long long I64;
: int primen;
: int prime[25000];
: I64 abs(I64 x)
: {
: .................（以下省略）


──── iamcs (Tue Sep  7 12:34:51 2004)   ─────────────

我自己写的abs

【 在 kinfkong ( Pegasus@zsu 天马  ) 的大作中提到: 】
:  我记得，abs()用在64bit interger里是有问题的，你改改试试
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 受不了！总是WA，完全按照你说的做的，奇怪。
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <math.h>
: : #include <time.h>
: : typedef long long I64;
: : int primen;
: : int prime[25000];
: .................（以下省略）


──── iamcs (Tue Sep  7 12:35:16 2004)   ─────────────

我郁闷的时候多了

【 在 infant (infant) 的大作中提到: 】
: hehe,实哥也有郁闷的时候,罕见丫 ^_^
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 受不了！总是WA，完全按照你说的做的，奇怪。
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <math.h>
: : #include <time.h>
: : typedef long long I64;
: : int primen;
: : int prime[25000];
: .................（以下省略）


──── iamcs (Tue Sep  7 12:52:15 2004)   ─────────────

!!! long long 的问题

【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: 改成这样就AC了，奇怪
: /////////////
: #include <stdio.h>
: #include <stdlib.h>
: #include <math.h>
: #include <time.h>
: typedef __int64 I64;
: int primen;
: int prime[25000];
: I64 abs(I64 x)
: .................（以下省略）


──── iamcs (Tue Sep  7 12:53:38 2004)   ─────────────

OK
大家去把
UVA 10392 和 ZOJ 1823 都干了！

【 在 iamcs (Savior) 的大作中提到: 】
: !!! long long 的问题
: 【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: : 改成这样就AC了，奇怪
: : /////////////
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <math.h>
: : #include <time.h>
: : typedef __int64 I64;
: : int primen;
: .................（以下省略）


──── iamcs (Tue Sep  7 12:54:52 2004)   ─────────────

是选的这个，不选这个long long 通不过编译的

【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: submit时选C++(GCC)
: 【 在 iamcs (Savior) 的大作中提到: 】
: : !!! long long 的问题
: : .................（以下省略）


──── dynamic (Tue Sep  7 12:55:31 2004)   ────────────

zoj那个不行的，呵呵

【 在 iamcs (Savior) 的大作中提到: 】
: OK
: 大家去把
: UVA 10392 和 ZOJ 1823 都干了！
: 【 在 iamcs (Savior) 的大作中提到: 】
: : !!! long long 的问题
: : .................（以下省略）


──── dynamic (Tue Sep  7 12:59:17 2004)   ────────────

嗯，对，都不行~
要写高精的

【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: UVA的是同一题
: 【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: zoj那个不行的，呵呵
: 【 在 iamcs (Savior) 的大作中提到: 】
: : OK
: : 大家去把
: : UVA 10392 和 ZOJ 1823 都干了！


──── iamcs (Tue Sep  7 13:01:27 2004)   ─────────────

哈，偶的可以。

【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: 嗯，对，都不行~
: 要写高精的
: 【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: : UVA的是同一题
: : zoj那个不行的，呵呵


──── dynamic (Tue Sep  7 13:03:06 2004)   ────────────

那题没有<2^54这个限制

【 在 iamcs (Savior) 的大作中提到: 】
: 哈，偶的可以。
: 【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: : 嗯，对，都不行~
: : 要写高精的


──── iamcs (Tue Sep  7 13:03:28 2004)   ─────────────

//ZOJ 1823 By Savior
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef long long I64;

int ansn;
I64 ans[100];

I64 abs(I64 x)
{
  return (x<0)?(-x):x;
}

I64 mod_mul(I64 x,I64 y,I64 n)
{  
  if(!x) return 0;
  return (((x&1)*y)%n+(mod_mul(x>>1,y,n)<<1)%n)%n;
}

I64 myrand()
{
  I64 a=rand();
  a*=rand();
  return abs(a);
}

I64 mod_exp(I64 a,I64 x,I64 n)
{  
  I64 ret=1;
  
  while(x) {
    if(x&1) ret=mod_mul(ret,a,n);
    a=mod_mul(a,a,n);
    x>>=1;
  }
  return ret;
}

I64 gcd(I64 x,I64 y)
{
  I64 q;

  while(1) {
    if(!y) return abs(x);
    q=x,x=y,y=q%y;
  }
}

bool Rabin_Miller(I64 n)
{
  I64 k=0,i,j,m,a;
  
  if(n<2) return 0;
  if(n==2) return 1;
  if(!(n&1)) return 0;
  m=n-1;
  while(!(m&1)) m>>=1,k++;
  for(i=0;i<20;i++) {
    a=myrand()%(n-2)+2;
    a=mod_exp(a,m,n);
    if(a==1) continue;
    for(j=0;j<k;j++) {
      if(a==n-1) break;
      a=mod_mul(a,a,n);
    }
    if(j<k) continue;
    return 0;
  }
  return 1;
}

I64 func(I64 x,I64 n)
{
  return (mod_mul(x,x,n)+1)%n;
}

void Pollard(I64 n)
{
  I64 i,x,y,p;

  if(Rabin_Miller(n)) {
    ans[ansn++]=n;
    return;
  }
  if(!(n&1)) {
    Pollard(2);
    Pollard(n>>1);
    return;
  }
  for(i=1;i<20;i++) {
    x=i;
    y=func(x,n);
    p=gcd(y-x,n);
    while(p==1) {
      x=func(x,n);
      y=func(func(y,n),n);
      p=gcd((y-x+n)%n,n)%n;
    }
    if(p==0 || p==n) continue;
    Pollard(p);
    Pollard(n/p);
    return;
  }
}

void output()
{
  int i,j;
  I64 tmp;

  for(i=0;i<ansn;i++)
    for(j=i+1;j<ansn;j++) if(ans[i]>ans[j])
      tmp=ans[i],ans[i]=ans[j],ans[j]=tmp;
  for(i=0;i<ansn;i++) printf("%lld\n",ans[i]);
  printf("\n");
}

int main()
{
  int casen;
  I64 n;

  srand((unsigned)time(NULL));

  while(scanf("%lld",&n)==1) {
    if(n<0) break;
    ansn=0;
    Pollard(n);
    output();
  }
  return 0;
}

【 在 iamcs (Savior) 的大作中提到: 】
: 哈，偶的可以。
: 【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: : 嗯，对，都不行~
: : 要写高精的


──── iamcs (Tue Sep  7 13:04:15 2004)   ─────────────

理论上会超的，可能没有这样的数据。

【 在 iamcs (Savior) 的大作中提到: 】
: //ZOJ 1823 By Savior
: #include <stdio.h>
: #include <stdlib.h>
: #include <math.h>
: #include <time.h>
: typedef long long I64;
: int ansn;
: I64 ans[100];
: I64 abs(I64 x)
: {
: .................（以下省略）


──── Jericho (Tue Sep  7 13:04:39 2004)   ────────────

1823早就写了，而且比你快，咔咔
【 在 iamcs (Savior) 的大作中提到: 】
: //ZOJ 1823 By Savior
: #include <stdio.h>
: #include <stdlib.h>
: #include <math.h>
: #include <time.h>
: typedef long long I64;
: int ansn;
: I64 ans[100];
: I64 abs(I64 x)
: {
: .................（以下省略）


──── iamcs (Tue Sep  7 13:05:26 2004)   ─────────────

是这样做的？

【 在 Jericho (Jericho) 的大作中提到: 】
: 1823早就写了，而且比你快，咔咔
: 【 在 iamcs (Savior) 的大作中提到: 】
: : //ZOJ 1823 By Savior
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <math.h>
: : #include <time.h>
: : typedef long long I64;
: : int ansn;
: : I64 ans[100];
: .................（以下省略）


──── dynamic (Tue Sep  7 13:05:37 2004)   ────────────

左移那一步应该先转unsigned long long

当然也有可能虽然越界了，但再取模之后可以保证结果是对的，可以考虑一下

【 在 iamcs (Savior) 的大作中提到: 】
: 理论上会超的，可能没有这样的数据。
: 【 在 iamcs (Savior) 的大作中提到: 】
: : //ZOJ 1823 By Savior
: : #include <stdio.h>
: : #include <stdlib.h>
: : #include <math.h>
: : #include <time.h>
: : typedef long long I64;
: : int ansn;
: : I64 ans[100];
: .................（以下省略）


──── Jericho (Tue Sep  7 13:06:29 2004)   ────────────

no....
【 在 iamcs (Savior) 的大作中提到: 】
: 是这样做的？
: 【 在 Jericho (Jericho) 的大作中提到: 】
: : 1823早就写了，而且比你快，咔咔
: : .................（以下省略）


──── iamcs (Tue Sep  7 13:07:52 2004)   ─────────────

数据弱，UVA的也弱。

【 在 Jericho (Jericho) 的大作中提到: 】
: no....
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 是这样做的？


──── dynamic (Tue Sep  7 13:11:33 2004)   ────────────

用的都是waterloo的数据

【 在 iamcs (Savior) 的大作中提到: 】
: 数据弱，UVA的也弱。
: 【 在 Jericho (Jericho) 的大作中提到: 】
: : no....


──── iamcs (Tue Sep  7 13:12:41 2004)   ─────────────

4611686014132420609
这个数据应该过不了

【 在 Jericho (Jericho) 的大作中提到: 】
: no....
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 是这样做的？


──── iamcs (Tue Sep  7 13:13:47 2004)   ─────────────

唉，他们为什么不搞一个
2147483647^2 ，这样就爽多了。

【 在 dynamic (Retired Prometheus) 的大作中提到: 】
: 用的都是waterloo的数据
: 【 在 iamcs (Savior) 的大作中提到: 】
: : 数据弱，UVA的也弱。


──── Jericho (Tue Sep  7 13:16:53 2004)   ────────────

nod.....
【 在 iamcs (Savior) 的大作中提到: 】
: 4611686014132420609
: 这个数据应该过不了
: 【 在 Jericho (Jericho) 的大作中提到: 】
: : no....


──── Jericho (Tue Sep  7 13:19:44 2004)   ────────────

我发觉我的是错的-_-，但可以过到数据而已。。。。
【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: 队长的好快，厉害，佩服
: 【 在 Jericho (Jericho) 的大作中提到: 】
: : 1823早就写了，而且比你快，咔咔
: : .................（以下省略）


──── magicpig (Tue Sep  7 13:28:17 2004)  ────────────


【 在 Jericho (Jericho) 的大作中提到: 】
: 我发觉我的是错的-_-，但可以过到数据而已。。。。
                        ------------------在比赛中，这个就是真理。        

: 【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: : 队长的好快，厉害，佩服


──── henryouly (Tue Sep  7 13:28:55 2004)   ───────────

又想起dy那句话：我不保证我的程序是对的，但是保证可以过评委所有数据
【 在 Jericho (Jericho) 的大作中提到: 】
: 我发觉我的是错的-_-，但可以过到数据而已。。。。
: 【 在 Mathematica (Lupus@zsu 天狼) 的大作中提到: 】
: : 队长的好快，厉害，佩服


──── zhi (Tue Sep  7 18:10:12 2004)   ──────────────

比赛中是真理,但是平时做题时还是认真点好

【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: 【 在 Jericho (Jericho) 的大作中提到: 】
: : 我发觉我的是错的-_-，但可以过到数据而已。。。。
:                         ------------------在比赛中，这个就是真理。        


──── magicpig (Tue Sep  7 18:22:15 2004)  ────────────

平时要踏实，比赛要学会“狡猾”。
zhi哥教训的是。
【 在 zhi (max@Apollo) 的大作中提到: 】
: 比赛中是真理,但是平时做题时还是认真点好
: 【 在 magicpig (Aquila@zsu 天鹰) 的大作中提到: 】
: :                         ------------------在比赛中，这个就是真理。        



--
※ 来源:. 逸仙时空 Yat-sen Channel bbs.zsu.edu.cn. [FROM: 192.168.54.155]
※ 修改:．iamcs 于 Sep 24 16:53:15 修改本文．[FROM: 192.168.54.155]