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原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬
查看更多关于【ACM算法竞赛日常训练】DAY10题解与分析【月月给华华出题】【华华给月月出题】| 筛法 | 欧拉的详细内容...