Problem 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 

 

Input

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).

 

Output

For each case, output “Case #k:” first, where k is the case number counting from 1.

Then output the answer to each query.

 

Sample Input
6 4 1 4 1 2 2 5 1 3 3 3 2 3 0 0

 

Sample Output
Case #1: 6 7

 

Author
xudyh

 

Source

 

Recommend
We have carefully selected several similar problems for you:  6297 6296 6295 6294 6293
考虑定义$a_i=\sum\limits_{d|i}^{n} f(d)$ 那么考虑题意中一个v需要加到哪几个$a_i$ 在原式中:$a_x+=v\times[gcd(x,n)=d]=v\times[gcd(x/d,n/d)=1]$ 然后可以套路反演一下$a_x+=v\times \sum\limits_{p|\frac{n}{d},p|\frac{x}{d}}\mu(p)$ 那么我们发现枚举$\frac{n}{d}$的所有约数的d倍就是我这次添加操作会影响的关于$a_x$的那些f数组的位置 所以添加$f(pd)+=v*\mu(p)$ 我们询问一个点$a[x]=\sum\limits_{d|x}f(d)$ $\sum\limits_{i=1}^{x}\sum\limits_{d|i}f(d)$可以枚举d $\sum\limits_{d=1}^{x}\frac{x}{d}f(d)$针对$\frac{x}{d}$数论分块即可 然后树状数组求前缀和 查询的时候树状数组求和即可

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论