SHARE
TWEET

mockvita

a guest Jun 22nd, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import math
  2. import sys
  3. sys.setrecursionlimit(1500)
  4.  
  5.  
  6. dp = {}
  7.  
  8.  
  9. def getDivisorCount(n):
  10.     rootN = int(math.sqrt(n))
  11.     divisors = []
  12.     for num in range(1, rootN + 1):
  13.         if(n % num == 0):
  14.             a = int(n / num)
  15.             # check for perfect square
  16.             if a * a == n:
  17.                 divisors.append(a)
  18.             else:
  19.                 divisors.append(num)
  20.                 divisors.append(a)
  21.     # print(divisors)
  22.     return len(divisors)
  23.  
  24.  
  25. def validPermutation(n):
  26.     if(n == 1):
  27.         return 1
  28.     if(n == 2):
  29.         return 1
  30.     if(n == 3):
  31.         return 3
  32.     ans = 0
  33.     if n - 1 in dp:
  34.       ans += dp[n - 1]
  35.     else:
  36.       dp[n - 1] = (n - 1) * validPermutation(n - 1)
  37.       ans += dp[n - 1]
  38.     if n - 2 in dp:
  39.       ans += dp[n - 2]
  40.     else:
  41.       dp[n - 2] = (n - 2) * validPermutation(n - 2)
  42.       ans += dp[n - 2]
  43.     dp[n] = ans
  44.     return ans
  45.  
  46.  
  47. t = int(input())
  48. for _ in range(t):
  49.     n = int(input())
  50.     divisorCount = getDivisorCount(n)
  51.     print(validPermutation(divisorCount))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top