7853: BZOJ3853：GCD Array
Memory Limit：64 MB
Time Limit：6 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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 Sigma(Xi) (i<=1<=X)
输入格式
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提示
没有写明提示
题目来源
By 镇海中学