清醒石
((stone.cpp))
题目背景
由于
顾z瞎开车，严重破坏了沝吅山的生态环境，导致了焚风效应，山女惠彤雪冻得瑟瑟发抖，所以她下山啦。
题目描述
山女惠彤雪做起了买“金刚壁·清醒石”的买卖。今天她有了第一个顾客(qwq)。从今天开始，连续(n)天，它每天会多一个新顾客。
为了顾客，他每天会去王小呆的迷宫里找(n)个清醒石。在第(i)天时，它会把这(n)块清醒石_平均分给_(i)个顾客,又为了顾客们不闹矛盾，他每天会分(尽可能多)的清醒石给顾客，并且每个顾客分的清醒石要(一样多)。由于山女每天睡不醒。所以她也需要清醒石。如果清醒石还有剩下，那就自己私吞了。
现在惠彤雪找到稳拿(NOIp500^+)的你，请你帮她算一算。对于每种(n)的情况，她一共会有多少颗清醒石来保持清醒。
输入输出格式
输入格式
第一行一个非负整数(T)表示询问组数。
接下来(T)行，每行一个正整数(n)表示询问。
输出格式：
输出(T)行，每一行输出询问对应的答案。
输入输出样例
输入样例#1：
1
5
输出样例#1：
4
样例解释：
第1天有1个客户，每人5个，剩下0个。
第2天有2个客户，每人2个，剩下1个。
第3天有3个客户，每人1个，剩下2个。
第4天有4个客户，每人1个，剩下1个。
第5天有5个客户，每人1个，剩下0个。
数据范围：
对于(10\%)的数据，满足(T=1,n<=10^6).
对于另外(30\%)的数据，满足(T<=10000，n<=10^{6}).
对于(100\%)的数据，满足(T<=10^7,n<=10^7).
题解
引子
由于惠彤雪冻得瑟瑟发抖，所以她不小心把题解的markdown给删了。只留了(PDF)，所以题解里的公式我放的是图片。大家请见谅。
那啥，给大家说个故事：从前，有一个魔王啦，他叫乘法逆元，有一群人，叫(OIer)啦。(OIers)遇到了一个小魔王：要求乘法逆元(QAQ).大家瞬间慌了。这时，英雄从天而降。告诉他们拓展欧几里德算法可以求乘法逆元。大家很高兴qwq，问题解决了，并且时间复杂度很优:(O(log^n_2)).可是有了更大的魔王。她要求(OIer)求出1-n所有数的逆元。大家又慌了。这时，又有一位英雄从天而降。告诉他们乘法逆元可以线性递推。大家很高兴，因为这样一来，世界上就没有魔王可以难住他们了。遇到单组询问。拓欧。多组询问。线性递推
这就是这道题出的原因。我怕有新的魔王难住大家，所以先告诉大家通关技巧啦(当然我不是英雄，只能算是小偷，偷来的秘籍分给大家)。观察可知，此题要求的是(sum_{i=1}^{n}n\%i)。
是看了秦江出的题后出的姊妹篇。不过，我要的是处理_多组询问_。
单组询问
我们先来说秦江的题。用数列分块+等差数列来做。都会吧。时间复杂度(O(sqrt{n}))的。很优。
其实我的题只能算是姊妹篇。真正升级版是大概是余数求和,要求的是(sum_{i=1}^{n}k\%i).大家快去领经验吧(qwq)。
多组询问
卧槽，这回数列分块就撑不住了QAQ。时间复杂度(O(Tsqrt{n})).分分钟卡包你GG了.总不能向魔王卑躬屈膝吧。我们当然有更优的方法。
开始我们真正的学习：
必备的前置知识：约数和定理，约数个数定理。
余数个数
(d(n))表示n的约数个数和。
计算d的方法：
prime[i]表示第i个质数。
num[i]表示i的最小因子的出现次数。
inline void OL(){
for(int i=2;i<=n;i++){
if(vis[i]==0){
tot++;
prime[tot]=i;
}
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
break;
}
}
}
我们之所以可以保证上述算法是线性的
就是因为：if (i%prime[j]==0) break
也就是说，每个数只会被 的最小质因子筛掉。
于是我们分三种情况
先放个链接透彻
i是质数
根据定理：d[i]=2,num[i]=1;
i%prime[j]==0
i%prime[i]!=0
根据上面的直接模拟，得出以下代码
void OLsss() {
d[1]=1; num[1]=1;
for (int i=2;i<N;i++) {
if (!vis[i]) {
prime[++tot]=i;
d[i]=2; num[i]=1;
}
for (int j=1;j<=tot&&prime[j]*i<N;j++) {
int v=prime[j]*i; no[v]=1;
if (i%prime[j]==0) {
num[v]=num[i]+1;
d[v]=d[i]/num[v]*(num[v]+1);
break;
}
d[v]=d[i]<<1; num[v]=1;
}
}
}
约数和
于是我们分三种情况
i是质数
(sd[i]=i+1.sp[i]=1+i);
i%prime[i]==0
i%prime[i]!=0
根据上面的直接模拟，得出以下代码
inline void Olsss() {
sd[1]=1; sp[1]=1;
for (int i=2;i<N;i+=) {
if (!vis[i]) {
prime[++tot]=i;
sd[i]=i+1; sp[i]=i+1;
}
for (int j=1;j<=tot&&prime[j]*i<N;j++) {
int v=prime[j]*i; vis[v]=1;
if (i%prime[j]==0) {
sp[v]=sp[i]*prime[j]+1;
sd[v]=sd[i]/sp[i]*sp[v];
break;
}
sd[v]=sd[i]*sd[prime[j]];
sp[v]=prime[j]+1;
}
}
}
然后。没了。