yukicoder No.16 累乗の加算 解説

問題文

前提知識

繰り返し二乗法

解説

まず、$(x^a)modb$を$O(log a)$で求める方法として、繰り返し二乗法というものがある。
どういうものかというと、
①まず事前に$x^1$,$x^2$,$x^4$,$x^8$...を求める。
②$a$&$1=1$なら解に$x^1$をかける、$a$&$2=2$なら解に$x^2$をかける...
というのを繰り返すことで、$x^a$を求める、というのが本髄。
この問題の制約は$N\leqq 100$かつ$A\leqq 10^9$なので、$O(NlogA)$は十分に間に合う。

そして、その繰り返し二乗法をどうやってコードに移すか。それは下記のコードを使えば計算可能である。

using ll=long long;
ll mod_pow(ll x,ll n,ll mo){
  //(x^n)%moを求める
  ll res=1;
  while(n>0){
    if(n&1)res=res*x%mo;
    x=x*x%mo;
    n>>=1;
  }
  return res;
}

また、atcoder/allを使えば
・modint::set_mod($1000003$)をする。
・$x$をmodint型に変更する。
これで$x.pow(A)$をすれば$x^amod1000003$が求まる。

これらを利用して$\sum_{i=1}^n x.pow(A)$をし、計算の都度$mod1000003$をとれば、解が求まる。

自作のmod_pow関数を使ったコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

ll mod_pow(ll x,ll n,ll mo){
  ll res=1;
  while(n>0){
    if(n&1)res=res*x%mo;
    x=x*x%mo;
    n>>=1;
  }
  return res;
}

int main(){
  ll x,n,ans=0;cin>>x>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++){
    ans+=mod_pow(x,a[i],1000003);
    ans%=1000003;
  }
  cout<<ans<<endl;
}

ACLのmodintを使ったコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using mint=modint;

int main(){
  mint::set_mod(1000003);
  ll n,x;cin>>x>>n;
  mint g=x,ans=0;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++){
    ans+=g.pow(a[i]);
  }
  cout<<ans.val()<<endl;
}