Codeforces Round #589 (Div. 2) C.Primes and Multiplication（质因数分解）-白红宇

Codeforces Round #589 (Div. 2) C.Primes and Multiplication（质因数分解）

阅读量：3899 次

发布时间：2019-05-23

本文共 770 字，大约阅读时间需要 2 分钟。

【题解】

题意：

定义 $prime(x)$ 为x的所有质因数的集合；

定义 $g(n,p)$ 为找到一个最大的整数 $p^k$ 使得n能被 $p^k$ 整除， $(p\in prime(x))$ ；

定义 $f(x,y)$ 为 $f(x,y)=\prod g(y,p)$ ， $(p\in prime(x))$ ；

给定x,n，要你输出 $ans=f(x,1)\cdot f(x,2) \cdot \cdot \cdot f(x,n)mod(1e9+7)$ 。

题解：

x有1e9，n有1e18，我们首先考虑到1e9范围内的数字最多有不超过10个素因数，所以先跑出x的素因数集合。然后我们考虑到对于每个p，只有当p能整除n时才对答案是有影响的，他可能是 $p^1,p^2,p^3....$ ，否则一定为1。具体怎么影响呢？我们举个栗子：

对于x=3,n=45

显然质因数只有3，对于3在范围内有影响的部分是所有的3的倍数，即有45/3=15个；

对于3^2的有45/9=5个；对于3^3的有45/27=1个；

所以答案就是 $3^{15}*3^5*3^1=3^{21}$ 对 $(1e9+7)$ 取模。

【代码】

#include 
   
    using namespace std;typedef long long ll;const int maxn=1e5+10;const ll mod=1e9+7;ll fac[100];int cnt=0;void init(ll x){    for(ll i=2;i*i<=x;i++){        if(x%i==0) fac[cnt++]=i,x/=i;        while(x%i==0) x/=i;    }    if(x>1) fac[cnt++]=x;}ll qpow(ll a,ll b){    ll ret=1;    while(b){        if(b&1) ret=ret*a%mod;        a=a*a%mod;        b>>=1;    }    return ret;}int main(){    ll x,n; scanf("%lld%lld",&x,&n);    init(x);    ll ans=1;    for(int i=0;i

转载地址：http://shfen.baihongyu.com/

你可能感兴趣的文章