随笔-2  评论-0  文章-0  trackbacks-0
 1#include<iostream>
 2#include<stdio.h>
 3#include<cmath>
 4#include<cstdlib>
 5#include<algorithm>
 6using namespace std;
 7long long mp(long long a,long long b,long long n)
 8{
 9    long long d=1,t=a;
10    while (b>0)
11    {
12        if (b%2==1) d=d*t%n;
13        b/=2;
14        t=t*t%n;
15    }

16    return d;
17}

18long long tu, tv;
19long long Gau(double x)
20{
21    if (x+1e-8>(long long)x) return (long long)x;
22    return (long long)x-1;
23}

24int main()
25{
26   long long p, M,  a, B, r, A, x, y,ta,tb;
27    while (scanf("%lld"&p) == 1)
28    {
29        if (p % 4 != 1)
30        {
31            printf("Illegal\n");
32            continue;
33        }

34        B = 1;
35        a = 2;
36        A = mp(a , (p - 1)/ 4,p);
37        while ((A * A + 1% p != 0)
38        {
39            a++;
40            A = mp(a , (p - 1)/ 4,p);
41        }

42        M = ((A * A + 1/ p);
43        tu = A%M;
44        tv = B%M;
45        while (M>1)
46        {
47               tu=A+M*Gau(0.5-double(A)/double(M));
48            tv=B+M*Gau(0.5-double(B)/double(M));
49            r=(tu*tu+tv*tv)/M;
50            ta=abs((tu*A+tv*B)/M);
51           tb=abs((tv*A-tu*B)/M);
52            A=ta;
53            B=tb;
54            M=r;
55        }

56          if(A>B)
57          swap(A,B);
58        printf("Legal %lld %lld\n", A, B);
59    }

60}

61
62
posted on 2010-09-02 10:34 Lancelot 阅读(256) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理