shunfurh
编程介的小学生
2017-11-16 05:44

Mophues

10
  • as
  • numbers
  • gcd
  • lines
  • each

Problem Description
As we know, any positive integer C ( C >= 2 ) can be written as the multiply of some prime numbers:
C = p1×p2× p3× ... × pk
which p1, p2 ... pk are all prime numbers.For example, if C = 24, then:
24 = 2 × 2 × 2 × 3
here, p1 = p2 = p3 = 2, p4 = 3, k = 4

Given two integers P and C. if k<=P( k is the number of C's prime factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( "gcd" means "greatest common divisor").

Please note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.

Input
The first line of input is an integer Q meaning that there are Q test cases.
Then Q lines follow, each line is a test case and each test case contains three non-negative numbers: n, m and P (n, m, P <= 5×105. Q <=5000).

Output
For each test case, print the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of P.

Sample Input
2
10 10 0
10 10 1

Sample Output
63
93

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

0条回答