fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. typedef unsigned long long ulong;
  4.  
  5. // Funkcja mnoży a i b mod n
  6. ulong MnozModulo(ulong a, ulong b, ulong n)
  7. {
  8.     ulong m,w;
  9.  
  10.     w = 0;
  11.     for(m = 1; m; m <<= 1)
  12.     {
  13.         if(b & m)
  14.             w = (w + a) % n;
  15.         a = (a << 1) % n;
  16.     }
  17.     return w;
  18. }
  19. // Funkcja oblicza a^e mod n
  20. ulong PotegujModulo(ulong a, ulong e, ulong n)
  21. {
  22.     ulong m,p,w;
  23.  
  24.     p = a;
  25.     w = 1;
  26.     for(m = 1; m; m <<= 1)
  27.     {
  28.         if(e & m)
  29.             w = MnozModulo(w,p,n);
  30.         p = MnozModulo(p,p,n);
  31.     }
  32.     return w;
  33. }
  34.  
  35. int main()
  36. {
  37.     int test,p,b,ile;
  38.     ulong d,x;
  39.     ulong a[3];
  40.     a[1]=2;
  41.     a[2]=3;
  42.     int i,j,s,n;
  43.     bool t;
  44.     scanf("%d",&test);
  45.     while(test--)
  46.     {
  47.         scanf(" %d %d",&p,&b);
  48.         ile=0;
  49.         do
  50.         {
  51.             if(p==2)
  52.                 ile++;
  53.             else if(p%2)
  54.             {
  55.                 s=0;
  56.                 for(d=p - 1; d % 2 == 0; s++)
  57.                     d /= 2;
  58.                 t = true;
  59.                 for(i = 1; i <= 2; i++)
  60.                 {
  61.                     x = PotegujModulo(a[i],d,p);
  62.                     if((x == 1) || (x == p - 1))
  63.                         continue;
  64.                     for(j = 1; (j < s) && (x != p - 1); j++)
  65.                     {
  66.                         x = MnozModulo(x,x,p);
  67.                         if(x == 1)
  68.                         {
  69.                             t = false;
  70.                             break;
  71.                         }
  72.                     }
  73.                     if(!t)
  74.                         break;
  75.                     if(x != p - 1)
  76.                     {
  77.                         t = false;
  78.                         break;
  79.                     }
  80.                 }
  81.                 if(t)
  82.                     ile++;
  83.             }
  84.             p++;
  85.         }
  86.         while(p<=b);
  87.         printf("%d\n",ile);
  88.     }
  89.     return 0;
  90. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2 
6 19 
12 50
stdout
copy 
5
10
https://ideone.com/mhN8KV
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!