code force 1228C

概述算是一题普通数论+思维题吧。 大概很多人是被题意绕晕了。   思路： 　　　首先常规 *** 作求出X的质因子。 　　　然后题目要求的是，X的每个质因子p，在g(i,p)的连乘。i∈[1,n]； 　　　我们转换下思维，不求每一个g(i,p)中最终是哪些 p的幂次，而是反求 每个p的幂次对结果的贡献。 　　　显而易见，p^k在1~n的出现的次数就是  [n/(p^k)]. 　　　这样枚举所有质因子，计算中再

算是一题普通数论+思维题吧。

大概很多人是被题意绕晕了。

 

思路：

　　　首先常规 *** 作求出X的质因子。

　　　然后题目要求的是，X的每个质因子p，在g(i,p)的连乘。i∈[1,n]；

　　　我们转换下思维，不求每一个g(i,p)中最终是哪些 p的幂次，而是反求 每个p的幂次对结果的贡献。

　　　显而易见，p^k在1~n的出现的次数就是  [n/(p^k)].

　　　这样枚举所有质因子，计算中再利用快速幂取模便可以得到答案

//#pragma comment(linker,"/STACK:1024000000,1024000000")//#pragma GCC optimize(2)#include <bits/stdc++.h>using namespace std;typedef double dou;typedef long long ll;typedef pair<int,int> pii;typedef map<int,int> mii;#define pai acos(-1.0)#define M 200007#define inf 0x3f3f3f3f#define mod 1000000007#define IN inline#define W(a) while(a)#define lowbit(a) a&(-a)#define left k<<1#define right k<<1|1#define lson L,mID,left#define rson mID + 1,R,right#define ms(a,b) memset(a,b,sizeof(a))#define Abs(a) (a ^ (a >> 31)) - (a >> 31)#define random(a,b) (rand()%(b+1-a)+a)#define false_stdio ios::sync_with_stdio(false),cin.tIE(0),cout.tIE(0)ll x,n;ll ans = 1;vector<ll>num;voID init(ll tmp) {    for (ll i = 2; i * i <= tmp; i++) {        if (tmp % i == 0) {            num.push_back(i);            W(tmp % i == 0)tmp /= i;        }    }    if (tmp != 1)num.push_back(tmp);}ll Pow(ll base,ll sup) {    ll sum = 1;    W(sup) {        if (sup & 1)sum = (sum * base) % mod;        sup >>= 1;        base = (base * base) % mod;    }    return sum % mod;}int main() {    false_stdio;    cin >> x >> n;    init(x);    for (auto p : num) {        ll tmp = 1;        W(tmp <= n / p) {//条件应该理解为  tmP*p<=n，而n%p==0,所以可以利用除法防止爆精度            tmp *= p;            ans = (ans * Pow(p,n / tmp)) % mod;        }    }    cout << ans << endl;    return 0;}

总结

以上是内存溢出为你收集整理的code force 1228C全部内容，希望文章能够帮你解决code force 1228C所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。