fork download
copy 
  1. from collections import Counter
  2. import random
  3.  
  4. T = int(input())
  5.  
  6. def gcd(x, y):
  7.   while y != 0:
  8.     x, y = y, x % y
  9.   return x
  10.  
  11. def is_prime(N):
  12.   if N == 1: return False
  13.   if N == 2 or N == 3 or N == 5: return True
  14.   if N % 2 == 0 or N % 3 == 0 or N % 5 == 0: return False
  15.   q = N - 1
  16.   e = 0
  17.   while q % 2 == 0:
  18.     q //= 2
  19.     e += 1
  20.   for i in range(10):
  21.     r = random.randint(2, N - 2)
  22.     r = pow(r, q, N)
  23.     if r == 1: continue
  24.     for _ in range(e - 1):
  25.       if r == N - 1: break
  26.       r = r * r % N
  27.       if r == 1: return False
  28.     if r != N - 1: return False
  29.   return True
  30.  
  31. def f(N, phi):
  32.   if N == 1: return []
  33.   if is_prime(N): return [N]
  34.   while phi % 2 == 0: phi >>= 1;
  35.   while True:
  36.     r = random.randint(1, N - 1)
  37.     g = gcd(r, N)
  38.     if g != 1: return f(N // g, phi) + f(g, phi)
  39.     r = pow(r, phi, N)
  40.     while r * r % N != 1:
  41.       r = r * r % N
  42.     if r != 1 and r != N - 1:
  43.       h = gcd(r - 1, N)
  44.       return f(N // h, phi) + f(h, phi)
  45.  
  46. def ff(N, phi):
  47.   g = gcd(N, phi)
  48.   if g == 1 or g == N: return f(N, phi)
  49.   ans = f(N // g, phi)
  50.   for p in ans[:]:
  51.     e = 0
  52.     while N % p == 0:
  53.       N //= p
  54.       e += 1
  55.     while g % p == 0:
  56.       g //= p
  57.       ans.append(p)
  58.     for _ in range(e - 1):
  59.       phi //= p
  60.     phi //= p - 1
  61.   return ff(N, phi) + ans
  62.  
  63. for _ in range(T):
  64.   N, phi = map(int, input().split())
  65.   ans = ff(N, phi)
  66.   ans = dict(Counter(ans))
  67.   print(len(ans))
  68.   for k in sorted(ans.keys()):
  69.     print(k, ans[k])
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:1:1: error: ‘from’ does not name a type
 from collections import Counter
 ^~~~
prog.cpp:35:3: error: expected unqualified-id before ‘while’
   while True:
   ^~~~~
stdout
copy 
Standard output is empty
https://ideone.com/YVWRnq
language:
C++14 (gcc 8.3)
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!