結果

問題 No.2365 Present of good number
コンテスト
ユーザー unti
提出日時 2023-07-04 04:42:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 4,216 bytes
コンパイル時間 2,635 ms
コンパイル使用メモリ 218,048 KB
最終ジャッジ日時 2025-02-15 05:50:15
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>; 
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};


//　 ダイクストラ　ひーぷ　
/* dijkstra(G,s,dis)
    入力：グラフ G, 開始点 s, 距離を格納する dis
    計算量：O(|E|log|V|)
    副作用：dis が書き換えられる
*/
// グラフ　スタート　距離　ひとつ前
void dijkstra(const graph & g, ll s ,vector<ll> & d,vector<ll> &prev ){
   ll N = g.size() ; //頂点数
   d.resize(N,INF) ;
   prev.resize(N,INF) ;
   priority_queue<P,vector<P>,greater<P>> pq ;
   d[s]=0 ;
   pq.emplace(d[s],s) ;
   while(!pq.empty()){
       P p=pq.top() ;
       pq.pop() ;
       ll v= p.se;
       if(d[v]<p.fi) continue ;
       for(auto & e :g[v]){
           if(d[e.to]>d[v]+e.cost){
               d[e.to]=d[v]+e.cost ;
               prev[e.to]=v ;  //頂点vを使ってe.toに辿り着いた
               pq.emplace(d[e.to],e.to) ;
           }
       }
    } 
}

/* get_path(prev, t)
    入力：dijkstra で得た prev, ゴール t
    出力： t への最短路のパス
*/
vector<ll> get_path(const vector<ll> &prev, ll t) {
    vector<ll> path;
    for (ll cur = t; cur != -1; cur = prev[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end()); // 逆順なのでひっくり返す
    return path;
}

map<ll,ll> factor(ll n){  //素因数とオーダーをマップで管理
  map <ll,ll> ord ;  
  for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            int res=0;
            while(n%i==0){
                n/=i;
                res++;
            }
            ord[i]=res;
        }
    }
  if(n!=1) ord[n]++;
  return ord ;
 }

vector< int > z_algorithm(const string &s) {
  vector< int > prefix(s.size());
  for(int i = 1, j = 0; i < s.size(); i++) {
    if(i + prefix[i - j] < j + prefix[j]) {
      prefix[i] = prefix[i - j];
    } else {
      int k = max(0, j + prefix[j] - i);
      while(i + k < s.size() && s[k] == s[i + k]) ++k;
      prefix[i] = k;
      j = i;
    }
  }
  prefix[0] = (int) s.size();
  return prefix;
}

const ll mod=1e9+7;

ll modpow(ll x, ll y){
  if(y==0) return 1;
  else{
    ll ans=modpow(x,y/2);
    ans=(ans*ans)%mod;
    if(y%2) return (ans*x)%mod;
    else return ans;
  }
}

const ll mmod=1e9+6;

ll mmodpow(ll x, ll y){
  if(y==0) return 1;
  else{
    ll ans=mmodpow(x,y/2);
    ans=(ans*ans)%mmod;
    if(y%2) return (ans*x)%mmod;
    else return ans;
  }
}

int main(){
  
  ll n,k; cin>>n>>k;
  
  map<ll,ll> mp;
  ll nn=n;
  for(ll i=2;i*i<=nn;++i){
    while(n%i==0){
      n/=i; mp[i]++;
    }
  }

  if(n!=1) mp[n]++;

  ll MA=0ll;
  for(auto u:mp) chmax(MA,u.fi);


  while(k>0&&MA>3){
    k--;  
    map<ll,ll> pm;
    for(auto u:mp){  
      ll num=u.fi+1;
      ll p=u.se;
      map<ll,ll> f=factor(num);
      for(auto v:f) pm[v.fi]+=v.se*p;
    }
    mp=pm;
    MA=0ll;
    for(auto u:mp) chmax(MA,u.fi);
  }


  if(!k){
    ll ans=1;
    for(auto u:mp){
      ll p=modpow(u.fi,u.se);
      ans*=p;
      ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
  }

  ll a=mp[2]; ll b=mp[3];
  
  ll ans=a;
  ll bns=b;
  ans*=mmodpow(2ll,k/2);
  bns*=mmodpow(2ll,k/2);
  ans%=mmod; bns%=mmod;
  
  if(k%2){
    bns*=2; bns%=mmod;
    swap(ans,bns);
  }

  ll p=modpow(2,ans);
  ll q=modpow(3,bns);

  //cout<<p<<" "<<q<<endl;

  p*=q; p%=mod;
  cout<<p<<endl;

  
}
0