#P17622. [qaswed12 OI R1] Function
[qaswed12 OI R1] Function
题目描述
定义函数 满足:
$$f(x)=\sum\limits_{i=0}^x{x\choose i}(-1)^{\gcd(x,i)}.$$特别的,。
给定一个长度为 的序列 。
有 次操作,操作分为两种:
1 l r k,表示 。2 l r,表示查询 。
答案可能会比较大,请对 取模。
输入格式
第一行,两个正整数 。
第二行, 个整数,表示序列 。
接下来 行,每一行表示一个操作,输入方式见题目描述。
输出格式
对于每个操作二,输出一行,一个非负整数表示答案。
6 5
1 1 4 5 1 4
2 1 6
1 2 4 3
1 3 6 1
2 2 6
2 3 4
999999969
999999463
999999495
提示
样例解释
第一次询问的实际答案为
数据范围与说明
本题输入输出量较大,请使用较快的输入输出方式。
本题开启捆绑测试。
| 子任务编号 | 特殊性质 | 分值 | ||
|---|---|---|---|---|
| 无 | ||||
| ^ | ||||
| ^ | ||||
| 无 | ||||
| ^ | ||||
特殊性质 :保证对于每次操作,满足 。
特殊性质 :保证对于每次操作一,满足 。
对于 的数据,满足 ,。