Takefumi Yamamura's blog

This blog is for my memorandum about programming and English.

Happy Coding

This blog is for my memorandum

div2 srm 704 hard ModEquationEasy

Problem Statement

You are given the s n, K, and v.

Consider the following modular equation with n variables: (x[0] * x[1] * x[2] * ... * x[n-1]) mod K = v. How many solutions does it have?

Formally, we want to find the number of sequences (x[0], x[1], ..., x[n-1]) such that each x[i] is an integer between 0 and K-1, inclusive, and the product of all x[i] gives the remainder v when divided by K.

Please compute and return the number of such sequences, modulo 109+7.


I used dynamic programing.