fork(3) download
copy 
  1. #import resource
  2. import sys
  3. #resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
  4. #import threading
  5. #threading.Thread(target=main).start()
  6. #threading.stack_size(2**26)
  7. #sys.setrecursionlimit(10**6)
  8. mod=(10**9)+7
  9. #fact=[1]
  10. #for i in range(1,100001):
  11. #    fact.append((fact[-1]*i)%mod)
  12. #ifact=[0]*100001
  13. #ifact[100000]=pow(fact[100000],mod-2,mod)
  14. #for i in range(100000,0,-1):
  15. #    ifact[i-1]=(i*ifact[i])%mod
  16. from sys import stdin, stdout
  17. import bisect
  18. from bisect import bisect_left as bl
  19. from bisect import bisect_right as br
  20. import itertools
  21. import collections
  22. import math
  23. import heapq
  24. #from random import randint as rn
  25. #from Queue import Queue as Q
  26. def modinv(n,p):
  27.     return pow(n,p-2,p)
  28. def ncr(n,r,p):
  29.     t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
  30.     return t
  31. def ain():
  32.     return map(int,sin().split())
  33. def sin():
  34.     return stdin.readline().strip()
  35. def GCD(x,y):
  36.     while(y):
  37.         x, y = y, x % y
  38.     return x
  39. def isprime(x):
  40.     if(x==1):
  41.         return False
  42.     elif(x<4):
  43.         return True
  44.     for i in range(2,int(math.sqrt(x))+1):
  45.         if(x%i==0):
  46.             return False
  47.     return True
  48. """**************************************************************************"""
  49. w=[0]*1000001
  50. p=[]
  51. for i in range(2,1000001):
  52.     if(w[i]==0):
  53.         p.append(i)
  54.         for i in range(i+i,1000001,i):
  55.             w[i]=1
  56. ans=[]
  57. for _ in range(int(sin())):
  58.     n=int(sin())
  59.     if(n%mod==0):
  60.         print 1/0
  61.     n1=n
  62.     i=0
  63.     d={}
  64.     while(i<len(p) and n!=1):
  65.         if(n%p[i]==0):
  66.             d[p[i]]=0
  67.             while(n%p[i]==0):
  68.                 n/=p[i]
  69.                 d[p[i]]+=1
  70.         i+=1
  71.     if(n!=1):
  72.         d[n]=1
  73.     di=[]
  74.     for i in d:
  75.         di.append([i,d[i]])
  76.     prod=n1
  77.     for i,j in di:
  78.         prod/=i
  79.         prod*=(((i-1)*j)+i)
  80.     prod%=mod
  81.     n1%=mod
  82.     prod=(prod*modinv(n1,mod))%mod
  83.     ans.append(str(prod))
  84. stdout.write("\n".join(ans))
Success #stdin #stdout 0.41s 62796KB
comments (?)
stdin
copy 
2
2
6
stdout
copy 
500000005
500000006
https://ideone.com/NwbxUR
language:
Python (cpython 2.7.16)
created:
4 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!