AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 97. 约数之和    原题链接    困难

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-19 16:33:57 ,  所有人可见 ,  阅读 11143


52


12

题目描述

假设现在有两个自然数A和B,S是AB的所有约数之和。

请你求出S mod 9901的值是多少。

输入格式
在一行中输入用空格隔开的两个整数A和B。

输出格式
输出一个整数,代表S mod 9901的值。

数据范围
$0≤A,B≤5×10^7$

输入样例:
2 3
输出样例:
15
注意: A和B不会同时为0。

感谢@hkr04大佬指出本题目代码效率有点低,导致TLE.
现在已经加入剪枝优化AC了,大家可以放心食用.

正解

(数学(质因数分解,唯一分解定律,约数和公式),分治递归)
数学类分析
  1. 质因数分解,就是将一个数分解成为 ${p_1}^{c1} \times {p_2}^{c_2} \times … \times {p_n}^{c_n}$ 比如说$24={2}^{3}\times{3}^{1}$
  2. 唯一分解定律,就是字面意思
  3. 约数和公式,如下文所示
    ${A}^{B}=(1 \+ {p_1}^{1} \+ {p_1}^{2} \+ ..... \+ {p_1}^{B \* c_1}) \times (1 \+ {p_2}^{2} \+ ..... \+ {p_n}^{B \times c_2}$)
    $ sum(p,c)= {1} \+ {p} \+ {p^2} \+ … \+ {p^c} $
    然后呢我们可以通过分类以及乘法中的提取公因式法,将sum函数中c为奇数的公式和sum函数中c为偶数的公式推出。具体参考《算法竞赛进阶指南》,亦可以看我的cpp代码中的sum函数。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 9901
int a,b;
int ksm(int a,int b)//快速幂函数
{
    int ans=1;
    a%=Mod;
    while(b)
    {
        if (b&1)
            ans=ans%Mod*a;
        a=a%Mod*a%Mod;
        b>>=1;
    }
    return ans;
}
long long sum(int p,int c)
{
    if (c==0)
        return 1;
    if(c&1)
        return ((1+ksm(p,(c+1)>>1))*sum(p,(c-1)>>1))%Mod;//奇数的情况下
    else
        return ((1+ksm(p,c>>1))*sum(p,(c>>1)-1)+ksm(p,c))%Mod;//偶数的情况下
}
int main()
{
    cin>>a>>b;
    int ans=1;
    for (int i=2;i<=a;i++)
    {
        int s=0;
        while(a%i==0)
        {
            s++;
            a/=i;
        }
        if (s)//这句话剪枝.然后就TLE变成了AC.by POJ
            ans=ans*sum(i,s*b)%Mod;
    } 
    if (a==0)
        cout<<0<<endl;//特判的情况,这里非常的阴毒,出题人用心险恶
    else
        cout<<ans<<endl;
    return 0;
}

36 评论


用户头像
有猷   2020-11-29 15:58      6    踩      回复

约数和公式似乎是
$$S=(1 + {p_1}^{1} + {p_1}^{2} + \dots + {p_1}^{B * c_1}) \times (1 + {p_2}^{2} + \dots + {p_2}^{B \times c_2}) \times \dots \times (1 + {p_n}^{1} + {p_n}^{2} + \dots + {p_n}^{B * c_n})$$


用户头像
佐助   2024-03-15 20:47      2    踩      回复

大佬们能帮忙解答吗 https://www.acwing.com/video/116/
错误.png


用户头像
XianZS.py   2024-09-21 16:55      1    踩      回复
print("牛逼")

用户头像
xyd   2023-03-15 20:49      1    踩      回复

大佬,还是你的代码适合我


用户头像
1548312   2024-03-16 16:48         踩      回复

hhhhh好搞笑最后一句注释


用户头像
江忍忍   2023-03-03 16:27         踩      回复

Orz


用户头像
God_Max_Me   2022-11-05 15:16         踩      回复

%%%%Orz


用户头像
山河相间灿若星河   2022-08-05 14:27         踩      回复

/WoW/


用户头像
种花家的老六   2022-07-28 14:13         踩      回复

∏ni=1∑B×cik=0pkiS=∏i=1n∑k=0B×cipik


用户头像
ωっ恭喜发财   2020-04-04 22:38         踩      回复

唯一分解,不是要求乘子是质因数吗,当i为4时 ,乘子不就不是质数了吗?

用户头像
planar   2020-05-01 22:06         踩      回复

2是质数哦

用户头像
OM14   2021-03-02 09:55         踩      回复

一开始我也想到这个问题,但实际上i从小到大,当i为4时,已经被i = 2整除完了,就不可能再被4整除了


用户头像
许可可可可   2019-11-28 22:20         踩      回复

nb!!!

用户头像
秦淮岸灯火阑珊   2019-11-30 18:12         踩      回复

QwQ


用户头像
Andrew82   2019-08-14 10:44         踩      回复

为什么是$A^B=\prod_{i=1}^{n}\sum_{k=0}^{B\times c_i}p_i^{k}$
不应该是$S=\prod_{i=1}^{n}\sum_{k=0}^{B\times c_i}p_i^{k}$,S为约数和

吗?

用户头像
秦淮岸灯火阑珊   2019-08-14 14:12         踩      回复

这里有解释,太旧了,我有点忘记这道题目的思路了


用户头像
Andrew82   2019-08-13 09:13         踩      回复

话说唯一分解好像可以写成$\sqrt(n)$的吧


用户头像
Idealthm   2019-08-01 19:45         踩      回复

为什么不直接用求和公式加上求逆元

用户头像
秦淮岸灯火阑珊   2019-08-01 20:13         踩      回复

我是按照yxc老师的方法做的.

用户头像
World_Devastator   2020-10-01 23:00    回复了 秦淮岸灯火阑珊 的评论         踩      回复

因为公式是(p^(n + 1) - 1)/(p - 1)
又因为要模9901所以在有一个点时,p^(n + 1) % 9901 = 1, 再减1是0,就错了
这个点是59407 3


用户头像
hkr04   2019-07-22 10:54         踩      回复

交到poj上会t掉

用户头像
秦淮岸灯火阑珊   2019-07-22 11:27         踩      回复

能不能把POJ这道题目的网址发我一下,我去康康,有什么区别.按理说我这道题目代码不会TLE.

用户头像
hkr04   2019-07-22 13:07    回复了 秦淮岸灯火阑珊 的评论         踩      回复

http://poj.org/problem?id=1845

用户头像
秦淮岸灯火阑珊   2019-07-22 15:12    回复了 hkr04 的评论         踩      回复

感谢已经修改完毕.


用户头像
robot_1   2019-05-30 23:56         踩      回复

请问if(c&1) 不就直接判断为奇数吗

用户头像
秦淮岸灯火阑珊   2019-05-31 17:36         踩      回复

是的啊,这样写速度快

用户头像
robot_1   2019-05-31 20:15    回复了 秦淮岸灯火阑珊 的评论         踩      回复

为什么偶数要加+ksm(p,c)

用户头像
摸鱼_L   2022-07-10 20:50    回复了 robot_1 的评论         踩      回复

次数是奇数但是数因为还有个零次幂的关系会是偶数个数,所以后面要加一下


用户头像
小乖乖   2019-05-30 22:29         踩      回复

用等比数列求和公式+对分母求逆元应该更快,二分求和为logn*logn,快速幂求逆元为logn


用户头像
墨辛   2019-02-22 11:23         踩      回复

ORZ

用户头像
..._4   2019-08-14 23:41         踩      回复

zbnb


用户头像
ì   2019-02-16 18:34         踩      回复

’‘’
return ((1+ksm(p,(c+1)>>1))sum(p,(c-1)>>1))%Mod;//奇数的情况下
else
return ((1+ksm(p,c>>1))
sum(p,(c>>1)-1)+ksm(p,c))%Mod;//偶数的情况下
‘’‘
在递归的过程中取模了无数次,但是按题目是smod9901,只取模了一次,为什么递归过程得到的结果是正确的?

用户头像
秦淮岸灯火阑珊   2019-02-16 19:50         踩      回复

这是可以的,因为取模运算是传递的啊.

用户头像
秦淮岸灯火阑珊   2019-02-16 19:50         踩      回复

而且你过程中如果不取模,那么你就会WA,除非你是高精度.

用户头像
秦淮岸灯火阑珊   2019-02-16 19:51         踩      回复

比如说,a%9901b和ab%9901是一样的

用户头像
ì   2019-02-17 11:59    回复了 秦淮岸灯火阑珊 的评论         踩      回复

吼的,谢谢(ง •_•)ง


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息