质数分解平方和

Lancelot — Thu, 02 Sep 2010 02:34:00 GMT

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

Lancelot 2010-09-02 10:34 发表评论

认真一些，做点事情，就这些

Lancelot — Fri, 27 Aug 2010 06:53:00 GMT

写给自己的BLOG。

Lancelot 2010-08-27 14:53 发表评论

C++博客-银白之翼

质数分解平方和

认真一些，做点事情，就这些