Product of divisors of a number from a given list of its prime factors | Python3 program to implement the above approach ; Function to calculate ( a ^ b ) % m ; Function to calculate and return the product of divisors ; Stores the frequencies of prime divisors ; Iterate over the prime divisors ; Update the product ; Update the count of divisors ; Driver Code
from collections import defaultdict NEW_LINE MOD = 1000000007 NEW_LINE def power ( a , b , m ) : NEW_LINE INDENT a %= m NEW_LINE res = 1 NEW_LINE while ( b > 0 ) : NEW_LINE INDENT if ( b & 1 ) : NEW_LINE INDENT res = ( ( res % m ) * ( a % m ) ) % m NEW_LINE DEDENT a = ( ( a % m ) * ( a % m ) ) % m NEW_LINE b >>= 1 NEW_LINE DEDENT return res % m NEW_LINE DEDENT def productOfDivisors ( p , n ) : NEW_LINE INDENT prime = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT prime [ p [ i ] ] += 1 NEW_LINE DEDENT product , d = 1 , 1 NEW_LINE for itr in prime . keys ( ) : NEW_LINE INDENT val = ( power ( itr , ( prime [ itr ] ) * ( prime [ itr ] + 1 ) // 2 , MOD ) ) NEW_LINE product = ( power ( product , prime [ itr ] + 1 , MOD ) * power ( val , d , MOD ) % MOD ) NEW_LINE d = ( d * ( prime [ itr ] + 1 ) ) % ( MOD - 1 ) NEW_LINE DEDENT return product NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 11 , 11 ] NEW_LINE n = len ( arr ) NEW_LINE print ( productOfDivisors ( arr , n ) ) NEW_LINE DEDENT