随笔-2  评论-0  文章-0  trackbacks-0
  置顶随笔
[置顶]认真一些，做点事情，就这些
写给自己的BLOG。
posted @ 2010-08-27 14:53 Lancelot 阅读(118) | 评论 (0) | 编辑 收藏
  2010年9月2日
质数分解平方和
 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 @ 2010-09-02 10:34 Lancelot 阅读(257) | 评论 (0) | 编辑 收藏
  2010年8月27日
认真一些，做点事情，就这些
写给自己的BLOG。
posted @ 2010-08-27 14:53 Lancelot 阅读(118) | 评论 (0) | 编辑 收藏
仅列出标题  
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 Lancelot