結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-07-01 00:11:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,821 bytes |
コンパイル時間 | 1,566 ms |
コンパイル使用メモリ | 179,480 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-07 11:46:24 |
合計ジャッジ時間 | 12,887 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 WA * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll =long long; #define all(v) v.begin(),v.end() #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) ll INF=2e18; const ll mod = 1000000006; const ll MOD=1000000000+7; class mint { public: long long x; mint(long long x=0) : x((x%mod+mod)%mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; template <class T> struct Matrix { vector<vector<T>> A; Matrix() {} Matrix(size_t n) :A(n,vector<T> (n,0)) {} Matrix(size_t n,size_t m) :A(n,vector<T> (m,0)) {} size_t height() const { return (A.size()); } size_t width() const { assert(height()!=0) ; return (A[0].size()); } inline const vector< T > &operator[](int k) const { return (A.at(k)); } inline vector<T> &operator[](int k) { return (A.at(k)); } void I() { assert(height()==width()); for(int i=0;i<height();i++) A[i][i]=1; return ; } Matrix &operator+=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(height()); while(k > 0) { if(k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix &operator%=(const ll &B) { size_t n = height(), m = width(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] %=B; return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } }; ll mod_pow(ll x,ll n,ll mod) { ll res=1; while(n>0) { if(n&1) { res=res*x%mod; } x=x*x%mod; n>>=1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N,K;cin>>N>>K; ll ma=500; vector<bool> note(ma+1); vector<ll> p(0); for(ll i=2;i<=ma;i++) { if(note[i]) continue; p.push_back(i); for(ll j=1;j*i<=ma;j++) { note[j*i]=true; } } ll n=N; for(ll i=2;i<=sqrt(N);i++) { while(n%i==0) { n/=i; } } if(n>1&&p.back()<n) p.push_back(n); ll k=(ll)p.size(); k=min(k,200LL); Matrix<mint> mat(k); Matrix<mint> a(k); for(ll i=0;i<k;i++) { for(ll j=0;j<k;j++) { ll t=(p[j]+1); ll count=0; while(t%p[i]==0) { t/=p[i]; count++; } mat[i][j]=count; } } a.I(); Matrix<mint> ans(k,1); for(ll i=0;i<k;i++) { ll count=0; while(N%p[i]==0) { count++; N/=p[i]; } ans[i][0]=count; } for(ll i=0;i<60;i++) { if(K&(1LL<<i)) { a*=mat; } mat*=mat; } a*=ans; mint an=1; for(ll i=0;i<k;i++) { ll t=a[i][0].x; an*=mod_pow(p[i],t,MOD); } cout<<an<<endl; }