CF1228C. Primes and Multiplication（数学）

发布时间：2020-12-16 09:12:29 所属栏目：百科来源：网络整理

导读：Let’s introduce some definitions that will be needed later. Let ??????????(??) be the set of prime divisors of ??. For example,??????????(140)={2,5,7},??????????(169)={13}. Let ??(??,??) be the maximum possible integer ???? where ?? is an

Let’s introduce some definitions that will be needed later.

Let ??????????(??) be the set of prime divisors of ??. For example,??????????(140)={2,5,7},??????????(169)={13}.

Let ??(??,??) be the maximum possible integer ???? where ?? is an integer such that ?? is divisible by ????. For example:

??(45,3)=9 (45 is divisible by 32=9 but not divisible by 33=27),
??(63,7)=7 (63 is divisible by 71=7 but not divisible by 72=49).
Let ??(??,??) be the product of ??(??,??) for all ?? in ??????????(??). For example:

??(30,70)=??(70,2)???(70,3)???(70,5)=21?30?51=10,
??(525,63)=??(63,3)???(63,5)???(63,7)=32?50?71=63.
You have integers ?? and ??. Calculate ??(??,1)???(??,2)?…???(??,??)mod(109+7).

Input
The only line contains integers ?? and ?? (2≤??≤109,1≤??≤1018) — the numbers used in formula.

Output
Print the answer.

Examples
inputCopy
10 2
outputCopy
2
inputCopy
20190929 1605
outputCopy
363165664
inputCopy
947 987654321987654321
outputCopy
593574252
Note
In the first example,??(10,1)=??(1,2)???(1,5)=1,2)=??(2,2)???(2,5)=2.

In the second example,actual value of formula is approximately 1.597?10171. Make sure you print the answer modulo (109+7).

In the third example,be careful about overflow issue.

思路：求出x的素因子，求其在1-n中所有数的贡献

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>
#include<string.h>
#include<vector>
#include<deque>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define bug printf("*********n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
typedef long long LL;
typedef long long ll;
const int MAXN = 150000 + 5;
const int mod = 1e9 + 7;
 
vector<LL>v;
LL qpow(LL a,LL b) {
    LL res = 1;
    while(b) {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
 
void primeFactor(LL n){
    LL tmp = n;
    if(n % 2 == 0) {
        v.push_back(2);
        while (n % 2 == 0) {
            n /= 2;
        }
    }
    for(LL i = 3; i * i <= tmp; i += 2){
        if(n % i == 0) {
            v.push_back(i);
        }
        while(n % i == 0){
            n /= i;
        }
    }
    if(n > 2)
        v.push_back(n);
}
int main()
{
    LL x,n;
    cin >> x;
    cin >> n;
    primeFactor(x);
    LL ans = 1;
    for(int i = 0; i < v.size(); i++) {
        LL tt = 0,nn = n;
        while(nn > 0) {
            nn /= v[i];
            tt += nn;
        }
        ans = (ans % mod * qpow(v[i],tt)) % mod;
    }
 
    cout << ans << endl;
 
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!