2480: GCD Array
内存限制:128 MB
时间限制:30.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:
Maintain an array a with index from 1 to l. There are two kinds of operations:
1. Add v to ax for every x that gcd(x,n)=d.
2. Query
输入
There are multiple test cases, terminated by a line "0 0".
For each test case, the first line contains two integers l,Q(1<=l,Q<=5*10^4), indicating the length of the array and the number of the operations.
In following Q lines, each line indicates an operation, and the format is "1 n d v" or "2 x" (1<=n,d,v<=2*10^5,1<=x<=l).
输出
For each case, output "Case #k:" first, where k is the case number counting from 1.
Then output the answer to each query.
样例输入 复制
6 4
1 4 1 2
2 5
1 3 3 3
2 3
0 0
样例输出 复制
Case #1:
6
7