Chef and Keyboard
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is a well known programmer. He owns a brand new Android phone of screen size of dimension n × m (n denotes the height of the phone and m denotes the width). Chef wants to design a program for painting the screen. He figured out c colors, which he will use to paint the screen. He wants to paint some rectangular section of pixels of the screen each with different color. Also Chef would like to use all of his c colors in painting.
Can you help Chef in finding number of different dimensions of rectangular section he can paint? In other words, find number of pairs x, y such that Chef can paint a rectangular section of dimension x × y (x denotes height, y denotes width) on the screen. Please note that Chef uses a fix orientation of his phone and is not allowed to rotate it, i.e. height always stays n and width always stays m and not the other way around.
First line of the input contains an integer T denoting the number of test cases. T test cases follow.
Only line of each test case contains three space separated integers n, m, c.
For each test case, output a single line containing the answer for the test case.
- 1 ≤ T ≤ 100
- 1 ≤ n, m ≤ 106
- 1 ≤ c ≤ 106
- Subtask #1: (40 points) 1 ≤ n, m ≤ 100, 1 ≤ c ≤ 104
- Subtask #2: (60 points) original constraints
Input: 2 4 6 12 3 3 10 Output: 3 0
Test case 1. Possible pairs of dimensions are (2, 6), (3, 4) and (4, 3). Note that the rectangular section of dimension (1, 12) can't be painted as it can't fit into the screen, because 12 > 6.
Test case 2. There does not exist any rectangle of desired dimensions which can have 10 different pixels painted.
|Tags||berezin, cakewalk, factorization, loop, oct16, simple-math|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.