fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     long MOD;
  7.  
  8.     class S {
  9.         long a, b;
  10.  
  11.         public S(long a, long b, long mod) {
  12.             this.a = (a + mod) % mod;
  13.             this.b = (b + mod) % mod;
  14.         }
  15.  
  16.         S mul(S o, long mod) {
  17.             return new S((a * o.a + 5 * b * o.b) % mod, (b * o.a + a * o.b) % mod, mod);
  18.         }
  19.  
  20.         S add(S o, long mod) {
  21.             return new S((a + o.a)%mod, (b + o.b)%mod, mod);
  22.         }
  23.     }
  24.  
  25.     public static long inv(long a, long mod) {
  26.         a %= mod;
  27.         long b = mod;
  28.         long p = 1, q = 0;
  29.         while (b > 0) {
  30.             long c = a / b;
  31.             long d;
  32.             d = a;
  33.             a = b;
  34.             b = d % b;
  35.             d = p;
  36.             p = q;
  37.             q = d - c * q;
  38.         }
  39.         return p < 0 ? p + mod : p;
  40.     }
  41.  
  42.     long pow (long a, long n, long MOD) {
  43.         long ret = 1;
  44.         for (; n > 0; n >>= 1, a = a * a % MOD) {
  45.             if (n % 2 == 1) {
  46.                 ret = ret * a % MOD;
  47.             }
  48.         }
  49.         return ret;
  50.     }
  51.  
  52.     void run() {
  53.         Scanner sc = new Scanner(System.in);
  54.         for (MOD = 2; MOD < 1000; ++MOD) {
  55.             boolean isPrime = true;
  56.             for (long div = 2; div < MOD; ++div) {
  57.                 isPrime &= MOD % div != 0;
  58.             }
  59.             if (MOD == 2 || !isPrime) continue;
  60.             if (MOD % 5 == 1 || MOD % 5 == 4 || MOD == 5) continue;
  61.             S g1 = new S(1, 0, MOD * MOD);
  62.             S g2 = new S(1, 0, MOD * MOD);
  63.             for (long  i = 1; i <=  MOD; ++i) {
  64.                 long i2 = inv(2, MOD * MOD);
  65.                 g1 = g1.mul(new S(i2-i, -i2, MOD * MOD), MOD * MOD);
  66.                 //g2 = g2.mul(new S(i2-i, -i2, MOD * MOD), MOD * MOD);
  67.             }
  68.             System.out.println("p=" + MOD + " a=" + g1.a + " a*2%(p*p)=" + (g1.a*2%(MOD*MOD))  + " b=" + g1.b + " A=" + (g1.b - 1) / MOD);
  69.         }
  70.     }
  71.  
  72.  
  73.     long sqrt5(long MOD) {
  74.         for (int i = 2; i < MOD; ++i) {
  75.             if (i * i % MOD == 5) return i;
  76.         }
  77.         throw new AssertionError();
  78.     }
  79.  
  80.  
  81.     public static void main(String[] args) throws FileNotFoundException {
  82.         new Main().run();
  83.     }
  84.  
  85.     static void tr(Object... objects) {
  86.         System.out.println(Arrays.deepToString(objects));
  87.     }
  88. }
  89.  
Success #stdin #stdout 0.22s 40768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
p=3 a=6 a*2%(p*p)=3 b=1 A=0
p=7 a=28 a*2%(p*p)=7 b=36 A=5
p=13 a=91 a*2%(p*p)=13 b=53 A=4
p=17 a=153 a*2%(p*p)=17 b=205 A=12
p=23 a=276 a*2%(p*p)=23 b=70 A=3
p=37 a=703 a*2%(p*p)=37 b=852 A=23
p=43 a=946 a*2%(p*p)=43 b=1506 A=35
p=47 a=1128 a*2%(p*p)=47 b=988 A=21
p=53 a=1431 a*2%(p*p)=53 b=796 A=15
p=67 a=2278 a*2%(p*p)=67 b=3954 A=59
p=73 a=2701 a*2%(p*p)=73 b=1388 A=19
p=83 a=3486 a*2%(p*p)=83 b=6060 A=73
p=97 a=4753 a*2%(p*p)=97 b=292 A=3
p=103 a=5356 a*2%(p*p)=103 b=1443 A=14
p=107 a=5778 a*2%(p*p)=107 b=2569 A=24
p=113 a=6441 a*2%(p*p)=113 b=7007 A=62
p=127 a=8128 a*2%(p*p)=127 b=14860 A=117
p=137 a=9453 a*2%(p*p)=137 b=14112 A=103
p=157 a=12403 a*2%(p*p)=157 b=22295 A=142
p=163 a=13366 a*2%(p*p)=163 b=327 A=2
p=167 a=14028 a*2%(p*p)=167 b=18204 A=109
p=173 a=15051 a*2%(p*p)=173 b=9689 A=56
p=193 a=18721 a*2%(p*p)=193 b=28372 A=147
p=197 a=19503 a*2%(p*p)=197 b=29945 A=152
p=223 a=24976 a*2%(p*p)=223 b=13604 A=61
p=227 a=25878 a*2%(p*p)=227 b=17026 A=75
p=233 a=27261 a*2%(p*p)=233 b=25864 A=111
p=257 a=33153 a*2%(p*p)=257 b=36238 A=141
p=263 a=34716 a*2%(p*p)=263 b=45500 A=173
p=277 a=38503 a*2%(p*p)=277 b=8865 A=32
p=283 a=40186 a*2%(p*p)=283 b=76694 A=271
p=293 a=43071 a*2%(p*p)=293 b=78818 A=269
p=307 a=47278 a*2%(p*p)=307 b=56182 A=183
p=313 a=49141 a*2%(p*p)=313 b=68861 A=220
p=317 a=50403 a*2%(p*p)=317 b=84640 A=267
p=337 a=56953 a*2%(p*p)=337 b=12133 A=36
p=347 a=60378 a*2%(p*p)=347 b=101672 A=293
p=353 a=62481 a*2%(p*p)=353 b=112255 A=318
p=367 a=67528 a*2%(p*p)=367 b=368 A=1
p=373 a=69751 a*2%(p*p)=373 b=18651 A=50
p=383 a=73536 a*2%(p*p)=383 b=14172 A=37
p=397 a=79003 a*2%(p*p)=397 b=69079 A=174
p=433 a=93961 a*2%(p*p)=433 b=174500 A=403
p=443 a=98346 a*2%(p*p)=443 b=188276 A=425
p=457 a=104653 a*2%(p*p)=457 b=117907 A=258
p=463 a=107416 a*2%(p*p)=463 b=181497 A=392
p=467 a=109278 a*2%(p*p)=467 b=136365 A=292
p=487 a=118828 a*2%(p*p)=487 b=186035 A=382
p=503 a=126756 a*2%(p*p)=503 b=35211 A=70
p=523 a=137026 a*2%(p*p)=523 b=230644 A=441
p=547 a=149878 a*2%(p*p)=547 b=283894 A=519
p=557 a=155403 a*2%(p*p)=557 b=157075 A=282
p=563 a=158766 a*2%(p*p)=563 b=109786 A=195
p=577 a=166753 a*2%(p*p)=577 b=175409 A=304
p=587 a=172578 a*2%(p*p)=587 b=315807 A=538
p=593 a=176121 a*2%(p*p)=593 b=278118 A=469
p=607 a=184528 a*2%(p*p)=607 b=60094 A=99
p=613 a=188191 a*2%(p*p)=613 b=11035 A=18
p=617 a=190653 a*2%(p*p)=617 b=1235 A=2
p=643 a=207046 a*2%(p*p)=643 b=374227 A=582
p=647 a=209628 a*2%(p*p)=647 b=319619 A=494
p=653 a=213531 a*2%(p*p)=653 b=302993 A=464
p=673 a=226801 a*2%(p*p)=673 b=377554 A=561
p=677 a=229503 a*2%(p*p)=677 b=446144 A=659
p=683 a=233586 a*2%(p*p)=683 b=72399 A=106
p=727 a=264628 a*2%(p*p)=727 b=284258 A=391
p=733 a=269011 a*2%(p*p)=733 b=184717 A=252
p=743 a=276396 a*2%(p*p)=743 b=196896 A=265
p=757 a=286903 a*2%(p*p)=757 b=150644 A=199
p=773 a=299151 a*2%(p*p)=773 b=10823 A=14
p=787 a=310078 a*2%(p*p)=787 b=456461 A=580
p=797 a=318003 a*2%(p*p)=797 b=116363 A=146
p=823 a=339076 a*2%(p*p)=823 b=236202 A=287
p=827 a=342378 a*2%(p*p)=827 b=591306 A=715
p=853 a=364231 a*2%(p*p)=853 b=45210 A=53
p=857 a=367653 a*2%(p*p)=857 b=534769 A=624
p=863 a=372816 a*2%(p*p)=863 b=258038 A=299
p=877 a=385003 a*2%(p*p)=877 b=53498 A=61
p=883 a=390286 a*2%(p*p)=883 b=249007 A=282
p=887 a=393828 a*2%(p*p)=887 b=190706 A=215
p=907 a=411778 a*2%(p*p)=907 b=222216 A=245
p=937 a=439453 a*2%(p*p)=937 b=825498 A=881
p=947 a=448878 a*2%(p*p)=947 b=174249 A=184
p=953 a=454581 a*2%(p*p)=953 b=897727 A=942
p=967 a=468028 a*2%(p*p)=967 b=387768 A=401
p=977 a=477753 a*2%(p*p)=977 b=587178 A=601
p=983 a=483636 a*2%(p*p)=983 b=407946 A=415
p=997 a=497503 a*2%(p*p)=997 b=11965 A=12
https://ideone.com/pw0QsN
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!