#785919 (C++23) No.2007 Arbitrary Mod (Easy)

提出ソース

結果

問題	No.2007 Arbitrary Mod (Easy)
ユーザー	tatananonano
提出日時	2022-08-07 03:32:06
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	6,479 bytes
コンパイル時間	2,253 ms
コンパイル使用メモリ	164,424 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-16 21:49:49
合計ジャッジ時間	4,566 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <set>
#include <map>
#include <ctime>
#include <stack>
#include <functional>
#include <cstdio>
#include <string>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double LD;
typedef double D;
typedef pair<ll,ll> P;
typedef pair<LD,LD> PD;
typedef map<ll,ll> M;
#define PQ priority_queue
#define PQD PQ<P,vector<P>,greater<P>>
#define PQS PQ<ll,vec,greater<ll>>
typedef vector<ll> vec;
typedef vector<string> ves;
typedef vector<vec> mat;
#define cing(a,b,c) a[b].pb(c);a[c].pb(b);
#define bit(n) (1LL<<(n))
const ll INF = bit(60);
//const ll INF = 8e18;
#define fi first
#define se second
#define cauto const auto&
#define rep(i,n) for(long long int i=0;i<n;i++)
#define rrep(i,n) for(long long int i=1;i<n;i++)
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define jep(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define REP(i, n) FOR(i, 0, n)
#define fore(i,a) for(const auto &i:a)
#define all(x) (x).begin(),(x).end()
#define frac(x) x-floor(x)
#define eb emplace_back
#define pb push_back
#define pbd(x,y) push_back({x,y});
#define pbt(x,y,z) push_back({x,y,z});
#define bs binary_search 
#define lb lower_bound
#define ub upper_bound
#define SUM(x) accumulate(all(x),0)
#define PS(a,b) partial_sum(all(a),begin(b))//累積和(具体的にはbは個数以外空にしておいて格納されていく)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end()) //重複消去＆sort
#define fr(f,x) fixed<<setprecision(f)<<x //小数点以下f桁までの表示
#define TFU(s) transform(all(s),begin(s),::toupper);//alphabetで全て大文字にする
#define TFL(s) transform(all(s),begin(s),::tolower);//alphabetで全て小文字にする
#define replace(s,a,A) replace(all(s),'a','A')//文字列sのaをAに変換する
#define NP(a) next_permutation(all(a))//順列
#define in(a, b, x) (a<=x&&x<b)//a以上b未満
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする
#define printd(n,x) cout<<fixed<<setprecision(n)<<x<<endl
#define cinv(a,n); rep(i,n){cin>>a[i];}
#define cinvv(a,n,m); rep(i,n){rep(j,m){cin>>a[i][j];}}
template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;}
//const ll mod = 1000000009;//手動で切り替える.
//const ll mod = 998244353;
const ll mod = 1000000007;
ll modpow(ll a,ll n,ll mod){if(mod==1)return 0;ll ret=1;ll p=a%mod;while(n){if(n&1)ret=ret*p%mod;p=p*p%mod;n>>=1;}return ret; }
M factor(ll n) {M ret;for(ll i=2;i*i<=n;i++){while(n%i==0){ret[i]++;n /= i;}}if(n != 1){ret[n]=1;}return ret;}//素因数分解 mapにする
vec divisor(ll n){vec K;for(ll i=1;i*i<=n;i++){if(n%i==0){K.pb(i);if(i*i!=n)K.pb(n/i);}}sort(all(K));return K;}//約数列挙 cauto& a=divisor(100);的に書く
ll modlog(ll a,ll b,ll p){ll g=1;for(ll i=p;i;i/=2)(g*=a)%=p;g=gcd(g,p);ll t=1,c=0;for(;t%g;c++){if(t==b)return c;(t*=a)%=p;}if(b%g){return -1;}t/=g;b /= g;ll n=p/g,h=0,gs=1;for(;h*h<n; h++){(gs*=a)%=n;}unordered_map<ll,ll>bs;for(ll s=0,e=b;s<h;bs[e]=++s){(e *= a) %= n;}for(ll s = 0, e = t; s < n;){(e*=gs)%=n;s+=h;if(bs.count(e))return c+s-bs[e];}return -1;}//a^x≡b(modp) x_min
bool isprime(ll N){if(N==1){return false;}if(N==2){return true;}for(ll i=2;i*i<=N;i++){if(N%i==0)return false;}return true;}
//  /*
constexpr ll MAX = 3000000;ll fac[MAX],finv[MAX],inv[MAX];//int main(){cominit();}と打つのを忘れないように.
void cominit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}
ll binom(ll n,ll k){if(n<k) return 0;if(n<0||k<0) return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}
ll hom(ll n,ll k){if(n==0&&k==0) return 1;return binom(n+k-1,k);}
ll pom(ll n,ll k){if(n<k) return 0;return fac[n]*finv[n-k]%mod;}
//   */
mat binomial(ll n) {mat a(n+1,vec(n+1));rep(i,n+1)rep(j,i+1){if(j==0||j==i)a[i][j]=1;else a[i][j]=a[i-1][j-1]+a[i-1][j];}return a;}//O(n^2)
template<typename T>T phi(T n) {T ret=n;for(T i = 2; i * i <= n; i++){if(n % i == 0){ret -= ret / i;while(n % i == 0) n /= i;}}if(n > 1){ret -= ret / n;}return ret;}
template<typename T>T extgcd(T a, T b, T &x, T &y){T d = a;if(b != 0){d=extgcd(b,a%b,y,x);y -= (a / b) * x;}else {x = 1;y = 0;}return d;}
mat mat_mul(mat&a,mat&b){mat res(a.size(),vec(b[0].size()));rep(i,a.size()){rep(j,b[0].size()){rep(k,b.size()){(res[i][j]+=a[i][k]*b[k][j])%=mod;}}}return res;}
mat matpow(mat a,ll n){mat res(a.size(),vec(a.size()));rep(i,a.size())res[i][i]=1;while(n>0){if(n & 1)res=mat_mul(a,res);a=mat_mul(a,a);n>>=1;}return res;}
           /*
#include <atcoder/all>
using namespace atcoder;
using mint =modint998244353;
//using mint =modint1000000009;
//using mint =modint1000000007;
#define FT(x) fenwick_tree<ll x> 
#define SA(s) vec suffix_arry(s)
#define LCP(s,a) vec lcp_rray(s,a)
#define ZA(s) z_algorithm(s)
#define IV(x,m) inv_mod(x,m)
#define FS(n,m,a,b) floor_sum(n,m,a,b)
#define FFT(a,b,c) vec a=convolution(b,c)
           */
void ACC(vec a,vec &b){b[0]=0;rrep(i,a.size()){b[i]=b[i-1]+a[i-1];}return;}

/*

struct BIT_Predecessor {
ll N, lg;
vector<int> data;
BIT_Predecessor() = default;
BIT_Predecessor(ll size) { init(size); }
void init(ll size) {N=size+2;data.assign(N+1,0);lg=31-__builtin_clz(N);}
void insert(ll k){if(get(k)== 1)return;for (++k; k <= N; k += k & -k) data[k] += 1;}
void reset(ll k) {if (get(k) == 0) {return;}for (++k; k <= N; k += k & -k) data[k] -= 1;}
ll sum(int k) const {ll ret = 0;for (++k; k; k -= k & -k) {ret += data[k];}return ret;}
ll get(ll k) const { return sum(k) - sum(k - 1); }
ll find_next(ll i) const {ll w = sum(i - 1);ll x = 0;for (ll k = 1 << lg; k; k >>= 1) {if (x + k <= N && data[x + k] <= w) {w -= data[x + k];x += k;}}if (x == N) {return -1;}return x;}
ll find_prev(ll i) const {ll w = sum(i) - 1;if (w < 0) {return -1;}ll x = 0;for (ll k = 1 << lg; k; k >>= 1) {if (x + k <= N && data[x + k] <= w) {w -= data[x + k];x += k;}}return x;}};

*/




int main(){
cout<<mod<<endl;
ll a,n;cin>>a>>n;
cout<<modpow(a,n,mod)<<endl;
}

yukicoder

結果

テストケース

ソースコード