共计 2989 个字符，预计需要花费 8 分钟才能阅读完成。
DAY10 共 2 题：
- 月月给华华出题
- 华华给月月出题
难度较大。
🎈 作者：Eriktse
🎈 简介：211 计算机在读，现役 ACM 银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换 C ++/Python 算法。（优质好文继续更新中……）🚀
🎈 原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1104.html
在做明天这两道题之前，强烈建议先看这篇文章《【ACM 数论】和式变换技术，兴许是最好的解说之一》。
月月给华华出题
题目传送门：https://ac.nowcoder.com/acm/problem/23048
当 N = n 时，咱们能够失去以下式子：
$$ans_n = \sum_{i=1}^{n}\frac{i}{gcd(i, n)}$$
依据咱们的教训，在 gcd 不不便确定的状况下，能够新增枚举变量，即新增一个 d 变量来枚举gcd(i, n)，如下：
$$\sum_{d|n}\sum_{i=1}^{n}[gcd(i, n) = d]\frac{i}{d}$$
接下来令i = id，失去上面的式子：
$$\sum_{d|n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]$$
无妨将 n/d 间接变为 d，这个对后果是没有影响的，因为枚举的都是n 的因子罢了。
$$\sum_{d|n}\sum_{i=1}^{d}i[gcd(i,d)=1]$$
前面这一坨的后果是：
$$\sum_{i=1}^{d}i[gcd(i,d)=1] = \frac{d \times \phi(d)}{2}$$
简略证实：咱们晓得
gcd(i, n) = gcd(n - i, n)，所以和n的gcd相等的数总是对称呈现的，因而若gcd(i, n) = 1，则必然有gcd(n - i, i) = 1，也就是说和n互质的所有数的平均值为n/2，将平均值乘上个数phi[n]即为“与 n 互质的所有正整数之和”。
留神当 n = 1 时，该当非凡解决，因为此时n - 1 = 1会产生计数缺失。
而对于n > 1的状况，如果要满足n - i = i则n为偶数，而此时n / 2必然不与n互质，所以计数是精确的。
于是最终后果为：
$$ans_n=\sum_{d|n}\frac{d \times \phi(d)}{2}$$
用欧拉筛筛出 phi（欧拉函数），而后枚举d，向d 的所有倍数加上奉献即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9;
int phi[N], ans[N];
//phi[n] = n * ((p1 - 1) / p1) * ((p2 - 1) / p2) * ... * ((pk - 1) / pk), 其中 p 为不同的质数
void init(int n)
{
bitset<N> vis;
vector<int> prim;
// 初始化 vis[1]和 phi[1]
vis[1] = true, phi[1] = 1;
for(int i = 2;i <= n; ++ i)
{// 当 i 没被筛掉，阐明是一个质数，退出 prim 数组中并设置 phi[i] = i - 1
if(!vis[i])prim.push_back(i), phi[i] = i - 1;
// 上面这个循环在更新 i * prim[j]的一些属性
for(int j = 0;j < prim.size() && i * prim[j] <= n; ++ j)
{vis[i * prim[j]] = true;// 乘上了一个质数，那么 i * prim[j]必定不是质数了
if(i % prim[j] == 0)
{// 此时 i 外面曾经蕴含 prim[j]，阐明 i * prim[j]没有呈现新的质因子
phi[i * prim[j]] = phi[i] * prim[j];
break;
}
phi[i * prim[j]] = phi[i] * (prim[j] - 1);
}
}
}
signed main()
{int n;scanf("%lld", &n);
init(n);
for(int i = 2;i <= n; ++ i)// 枚举所有 d = i
{for(int j = 1;i * j <= n; ++ j)// 枚举所有 d 的倍数 i * j
{ans[i * j] += i * phi[i] / 2;
}
}
// 这里答案 + 1 是加上当 d = 1 时的后果
for(int i = 1;i <= n; ++ i)printf("%lld\n", 1 + ans[i]);
return 0;
}华华给月月出题
题目传送门：https://ac.nowcoder.com/acm/problem/23047
这题的式子不必推，重点在于如何疾速求到:
$$i^n,i \in [1, n]$$
如果用疾速幂的话，总复杂度达到了O(nlogn)，这道题的n <= 1.3e7，卡着不让间接用疾速幂。
咱们思考一个问题，如果将一个数字 a 质因数分解，咱们能够不能够利用其质因子的 n 次方来求得 a 的n次方呢？
如果你晓得 i^n 是一个积性函数，这一段就能够跳过了。
假如 a 由m种质数相乘失去：
$$a=p_1^{k_1}\times p_2^{k_2}\times … \times p_m^{k_m}$$
那么有：
$$ a^n=(p_1^{k_1}\times p_2^{k_2}\times … \times p_n^{k_n})^n $$
把 n 放进去：
$$ a^n=p_1^{nk_1}\times p_2^{nk_2}\times … \times p_n^{nk_n} $$
而后做一点点变动:
$$ a^n=(p_1^{n})^{k_1}\times (p_2^{n})^{k_2}\times … \times (p_n^{n})^{k_n} $$
也就是说咱们的 a^n 能够通过 p1^n, p2^n... 转移过去。
接下来写个筛法即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1.3e7 + 9, p = 1e9 + 7;
int a[N];
int qmi(int a, int b)
{
int res = 1;
while(b)
{if(b & 1)res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
void init(int n)
{
bitset<N> vis;
vector<int> prim;
vis[1] = 1, a[1] = 1;
for(int i = 2;i <= n; ++ i)
{
// 当 i 没被筛掉，阐明是一个质数
if(!vis[i])prim.push_back(i), a[i] = qmi(i, n);
// 上面这个循环在更新 i * prim[j]的一些属性
for(int j = 0;j < prim.size() && i * prim[j] <= n; ++ j)
{vis[i * prim[j]] = true;// 乘上了一个质数，那么 i * prim[j]必定不是质数了
// 新增一个质因子 prim[j]，那么只需乘上 prim[j]^n 即可
a[i * prim[j]] = a[i] * a[prim[j]] % p;// 不要遗记取模
//i^n 筛法无需分类
if(i % prim[j] == 0)break;
}
}
}
signed main()
{int n;scanf("%lld", &n);
init(n);
int ans = 0;
for(int i = 1;i <= n; ++ i)ans ^= a[i];
printf("%lld\n", ans);
return 0;
}🎈 本文由 eriktse 原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬
