FWFUNC - Fight with functions
English | Vietnamese |
Multiplicative functions are defined as functions such that f(m*n) = f(m) * f(n). Now, we put an extra constraint on multiplicative functions that if m and n are coprime , then f(m) and f(n) are also coprime. Additionally it is also provided that f(1)=1. f(x) is defined for positive integers and it returns positive integers.
Now, you are provided with some x and corresponding f(x). Your task is to find out , if you can uniquely determine the value of f(y) given y and if yes, find the value.
Input
The first line of input contains a number representing the number of test cases. For each test case, the first line contains a number N representing the number of (x,f(x)) pairs to be provided. N Lines follow, each line containing a pair of space separated numbers : the first one corresponding to x and second one to f(x). Next line contains q, the number of queries. q lines follow, each containing a number y.
Output
For each test case output q lines, one corresponding to each query. The output should contain "YES f(y)" where f(y) is replaced by the integer denoting f(y) with no leading zeroes if given the data, we can uniquely determine f(y), or "NO" if the input data is inconsistent with the properties of the function or with the given information provided about the function, we can not uniquely determine f(y).
Example
Input: 3 3 2 2 3 2 7 19 1 7 1 6 6 1 6 2 2 2 3 3 1 12 Output: NO YES 6 YES 12
Constraints
Dataset 1: The number of test cases are less than 20. N ≤=50. x and f(x) ≤ 10^50 . x and f(x) do not have a prime factor greater than 100005.
The number of queries are less than or equal to 50. Each number in the query is less than 10^50. You are guaranteed that if the answer is unique, it contains less than 400 digits. Time limit: 12s
Added by: | Race with time |
Date: | 2009-02-19 |
Time limit: | 1.090s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Code Craft 09 |