This Looks Like an A-Level Problem
Time limit2sMemory limit128 MB
Decide whether integer A can be repeatedly factored into integers whose product stays A while some factorization's sum equals B, using transitive transformations.
- Level
Hard8 of 10
- Topics
- Number theory, Math, Combinatorics
- Solved
- No attempts yet
Problem
Let X be an integer. If there are integers a_1, a_2, ..., a_n such that X = a_1 * a_2 * ... * a_n and Y = a_1 + a_2 + ... + a_n, then X is said to be able to transform into Y.
Also, if X can transform into some number Y, and Y can transform again into Z, then X can transform into Z.
Given two integers A and B, determine whether A can transform into B.
Input
The first line contains the number of test cases T. 1 <= T <= 100.
Each test case contains two integers A and B on one line. They satisfy -2^31 <= A, B <= 2^31 - 1.
Output
For each test case, print yes on one line if A can transform into B; otherwise print no.
Hint
Since 6 = 2 * 3 and 2 + 3 = 5, 6 can transform into 5.