CF1228C Primes and Multiplication


这场CF我网炸了 然后赛后补题 这道题应该算是魔改一下阶乘质因数分解 题意翻译直接搬洛谷的了懒得打

1.题意简述:

2.题解:

首先我们可以把$x$质因数分解 然后考虑$x$的因子$p$

对于每一个$p$ 我们都要求出$g(1,p)\cdot g(2,p)\cdots g(n,p)$ 而$g(x,p)$的含义其实就是对于$x$质因数分解后的$p^k$所以我们可以按阶乘分解那么考虑 考虑每个因子$p$对于答案的贡献 首先考虑$p$ 显然有$\lfloor \frac{n}{p} \rfloor$个数至少包含一个$p$ 那么贡献就是$p^{\lfloor \frac{n}{p} \rfloor}$

之后再考虑$p^2$ 有$\lfloor \frac{n}{p^2} \rfloor$个数可以分解出$p^2$ 但由于之前我们在统计$p$时已经加了一遍 所以这时候的贡献不需要乘2 只需要再加上$\lfloor \frac{n}{p^2} \rfloor$就好了

以此类推 总共需要统计$\log_{p}{n}$次 记贡献总数为$t$ 那么该$p$对答案的贡献便是$p^t$ 之后快速幂统计即可 要注意的是在统计贡献数时有可能会爆long long(实际上不会)我们不用考虑那么多 因为$t$是次幂不能直
接%mod 但是我们有欧拉定理 我们把次幂%phi(mod)答案是不变的 因为题目给的mod是$1e9+7$所以直接%(mod-1)即可

3.AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll x,n;
vector<ll> prime;
ll ksm(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    cin>>x>>n;
    for(ll i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            prime.push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) prime.push_back(x);
    ll l=prime.size();
    ll ans=1;
    for(int i=0;i<l;i++)
    {
        ll p=prime[i];
        ll t=n,t1=0;
        while(t)
        {
            t1=(t1+t/p)%(mod-1);
            t/=p;
        }
        ans=(ans%mod*ksm(p,t1)%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ3666 Making the Grade POJ3666 Making the Grade
题意简述:已知一个序列$A$ 找到一个单调不增或者单调不减的序列$B$ 使得$\sum_{i=1}^{n}|A_i-B_i|$最小 题解:这题首先有一个引理 每一个$B_i$都在$A$中出现过 考虑一下简单的证明 设$A’$为$A$
2019-10-05
下一篇 
Comet OJ Contest 8C 符文能量 Comet OJ Contest 8C 符文能量
题目大意:给定一个长度为$n$的二元组序列$(a_i,b_i)$ 对相邻的$i-1$和$i$合并两个二元组的代价为$b_{i-1}\cdot a_i$ 你还可以选择一个区间 使得这个区间的所有二元组变为$(k\cdot a_i,k\cdot
2019-08-27
  目录