code force 1228C
发布时间:2020-12-16 09:12:26 所属栏目:百科 来源:网络整理
导读:算是一题普通数论+思维题吧。 大概很多人是被题意绕晕了。 ? 思路: 首先常规操作求出X的质因子。 然后题目要求的是,X的每个质因子p,在g(i,p)的连乘。i∈[1,n]; 我们转换下思维,不求每一个g(i,p)中最终是哪些 p的幂次,而是反求 每个p的幂次对结果的贡献
算是一题普通数论+思维题吧。 大概很多人是被题意绕晕了。 ? 思路: 首先常规操作求出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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |