結果

問題 No.2365 Present of good number
ユーザー untiunti
提出日時 2023-07-04 04:01:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,938 bytes
コンパイル時間 2,563 ms
コンパイル使用メモリ 223,544 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-25 01:27:04
合計ジャッジ時間 4,983 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 1 ms
4,376 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 2 ms
4,380 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;
  }
}

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]++;


  while(k>0&&mp.size()>2){
    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;
  }


  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*=modpow(2ll,k/2);
  bns*=modpow(2ll,k/2);
  ans%=mod; bns%=mod;
  
  if(k%2){
    bns*=2; bns%=mod;
    swap(ans,bns);
  }

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

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

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

  
}
0