题解--Codeforces Round 680 [C. Division]
C. Division
Oleg’s favorite subjects are History and Math, and his favorite branch of mathematics is division.
To improve his division skills, Oleg came up with pairs of integers and and for each pair decided to find the greatest integer , such that:
- is divisible by ;
- is not divisible by .
Oleg is really good at division and managed to find all the answers quickly, how about you?
Input
The first line contains an integer () — the number of pairs.
Each of the following lines contains two integers and (; ) — the -th pair of integers.
Output
Print integers: the -th integer is the largest such that is divisible by , but is not divisible by .
One can show that there is always at least one value of satisfying the divisibility conditions for the given constraints.
样例
1 | 输入: |
算法1
分解质因数
参考文献
C++ 代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 klklkl's blogs!