洛谷 P1593 因子和 (升级版！)

2023-05-16

题目描述

已知一个等差数列{an}的首项为 $x^{y}$ ,且对于任意两个正整数 i，j 都存在ai+aj 也在该数列中,

求所有可能的公差 d 的和,答案对 99824353 取模。

输入输出格式

输入格式：

输入的第一行为两个正整数 x,y。

输出格式：

输出包括一行一个整数,代表所有可能的公差 d 的和。

输入输出样例

输入样例#1：

2 3

输出样例#1：

说明

对于 10%的数据,x,y<=10,

对于 30%的数据,x,y<=100000,

对于 70%的数据,x,y<=1e9 ,

对于 100%的数据,x,y<=1e15

比较有意思的一道数学题。通过一点点转换就可以变成洛谷的那道题了。

首先,对于任意的 $ai,aj,ai+aj$ 也在这个等差数列中。我们设 $aj=ai+md$ ， $ai+aj=2ai+md$ ， $\because ai+aj$ 也在数列中， $\therefore$ 设 $ai+aj=ai+md+nd$ ， $\therefore 2ai+md=ai+md+nd$ ，化简得 $n=\frac{ai}{d}$ 。 $\because$ $ai,n$ 都为整数， $\therefore d$ 为整数，所有数列所有公差 $d$ 的和为 $ai$ 的所有因子和。所以现在只要求出 $x^{y}$ 的所有因子和就行了。

先不管那个 $y$ 次方,从 $x$ 入手。对于任意一个数 $x$ ，将它质因数分解。随便举个例子，对于 $12$ ，质因数分解后变成了 $2^{2}\cdot 3^{1}$ ，它的因子则为 $2^{0}or3^{0}$ ， $2^{1}$ ， $3^{1}$ ， $2^{1}\cdot3^{1}$ ， $2^{2}\cdot3^{1}$ ，然后这些因子的和可以化为 $\left ( 2^{0}+2^{1}+2^{2} \right )\cdot\left ( 3^{0}+3^{1} \right )$ ，不信邪的同学可以把括号拆开来或者多列举几个数来试。因此，对于任意一个数 $x$ ，设其第 $i$ 个质因子为 $pi$ ，其最高次为 $ki$ ，所有因子的和则为 $\prod_{i=1}^{n}\sum_{j=0}^{ki}pi^{j}$

看起来这个东西很怪很难算，其实说简单点就是找到这个数每个质因子的最高次方，然后从1一直加到这个质因子的最高次方，然后把所求的和全乘起来就能得到答案了。

最后那个之前被丢弃的 $y$ 次方可以捡回来了。如果一个数 $x$ 的其中一个质因子 $p$ 的最高次方为 $k$ ，那么在 $x^{y}$ 中质因子 $p$ 的最高次方显然是 $k\cdot y$ ，所以只需要在最高次方上面乘个 $y$ 就行了。等比数列求和的话是数学必修的内容我就懒得说了直接套公式吧。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int p=998244353;
long long x,y,ans=1,tot=1;
inline LL qpow(LL a, LL n)//快速幂
{
    LL ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
inline LL niyuan(LL b)//求逆元
{
    return qpow(b%p,p-2);
}
inline LL solve(LL a,LL b)
{
    return ((qpow(a%p,b*y+1)-1))*(niyuan(a-1))%p;//等比数列求和
} 
int main()
{
    cin>>x>>y;
    int k=sqrt(x);
    if(k<2)
        k=x;
    for(int i=2;i<=k;i++)
    {
        register LL cnt=0;
        while(!(x%i))//找到因子(其实判断是不是质因子都无所谓了毕竟第一个枚举到的肯定就是质因子)
        {
            ++cnt;
            x/=i;
        }
        if(cnt)//cnt记录最高次方
            ans=(ans*solve((LL)i,cnt))%p;
    }
    if(x>1) ans=(ans*solve(x,1))%p;//补上最后一部分。
    cout<<ans%p;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)