結果
問題 | No.2365 Present of good number |
ユーザー |
|
提出日時 | 2023-06-30 22:41:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,544 bytes |
コンパイル時間 | 4,114 ms |
コンパイル使用メモリ | 260,324 KB |
最終ジャッジ日時 | 2025-02-15 04:17:44 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 WA * 23 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>#define SELECTER(_1,_2,_3,SELECT,...) SELECT#define rep1(i,n) for(int i=0;i<(int)n;++i)#define rep2(i,a,n) for(int i=(int)a;i<(int)n;++i)#define rep(...) SELECTER(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)#define RSELECTER(_1, _2, _3, RSELECT, ...) RSELECT#define rrep1(i,n) for(int i=(int)n-1;i>=0;--i)#define rrep2(i,a,n) for(int i=(int)n-1;i>=(int)a;--i)#define rrep(...) RSELECTER(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)#define all(a) a.begin(),a.end()#define rall(a) a.rbegin(),a.rend()#define fi first#define se second#define PrintR LogOutput#ifdef _DEBUG#define Log(...) LogOutput(__VA_ARGS__)#else#define Log(...)#endifusing namespace std;using namespace atcoder;using ll=long long;using pii=pair<int,int>;using pll=pair<long long,long long>;using pdd=pair<long double,long double>;using veci=vector<int>;using vecpii=vector<pair<int,int>>;using vecll=vector<long long>;using vecpll=vector<pair<long long,long long>>;using vecpdd=vector<pair<long double,long double>>;using vecs=vector<string>;using vecb=vector<bool>;using vecd=vector<long double>;template<class T> inline bool chmax(T& a,T b){if(a<b) {a=b;return true;} return false;}template<class T> inline bool chmin(T& a,T b){if(a>b) {a=b;return true;} return false;}constexpr ll INF=numeric_limits<ll>::max() / 4;constexpr ll MOD=998244353;using tp=tuple<int,int,int>;using tpll=tuple<ll,ll,ll>;using mint=modint998244353;using mint10=modint1000000007;template<typename T,typename std::enable_if_t<!is_same<T, mint>::value && !is_same<T, mint10>::value, nullptr_t> = nullptr>T LogOutput(T a, bool b = true){if(b) cout << a << endl;return a;}template <typename T,typename std::enable_if_t<is_same<T, mint>::value || is_same<T, mint10>::value, nullptr_t> = nullptr>auto LogOutput(T a, bool b = true) -> decltype(a.val()){if(b) cout << a.val() << endl;return a.val();}template<typename... Args>void LogOutput(Args&&... args){stringstream ss;((ss << LogOutput(args, false) << ' '), ...);cout << ss.str().substr(0, ss.str().length() - 1) << endl;}template<typename T>void LogOutput(vector<T>& data){for(int i = 0 ; i < data.size() ; ++i){cout << LogOutput(data[i], false) << " \n"[i == data.size() - 1];}}template<typename T>void LogOutput(vector<vector<T>>& data){for(auto d : data) LogOutput(d);}vecpii prime(int n){vecpii res;int m = n;for(int i = 2; i * i <= m ; ++i){int cnt = 0;while(n % i == 0) cnt++, n /= i;if(cnt) res.emplace_back(i, cnt);}if(n != 1) res.emplace_back(n, 1);return res;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;ll k;cin>>n>>k;auto t = prime(n);if(k < 30){rep(j, k){map<int, int> mp;rep(i, t.size()){auto u = prime(t[i].fi + 1);rep(p, u.size()){mp[u[p].fi] += u[p].se * t[i].se;}}t.clear();for(auto [l, r] : mp) t.emplace_back(l, r);}mint10 ans = 1;rep(i, t.size()){ans *= mint10(t[i].fi).pow(t[i].se);}cout<<ans.val()<<endl;return 0;}rep(j, 30){map<int, int> mp;rep(i, t.size()){auto u = prime(t[i].fi + 1);rep(p, u.size()){mp[u[p].fi] += u[p].se * t[i].se;}}t.clear();for(auto [l, r] : mp) t.emplace_back(l, r);}k -= 30;mint10 u = mint10(2).pow(k / 2);mint10 ans = 1;rep(i, t.size()){if(k % 2){ans *= mint10(t[i].fi == 2 ? 3 : 2).pow((u * t[i].se).val());}else{ans *= mint10(t[i].fi).pow((u * t[i].se).val());}}cout<<ans.val()<<endl;}