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 #define int long longusing 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 vis; vector 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 #define int long longusing 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 vis; vector 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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?