ddcc2018_qual_c ~重複しないように片方をうまく分離する~

Quiz

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c

AC code

https://atcoder.jp/contests/ddcc2019-qual/submissions/13110019

考察

  • O(N)で解ければいい
  • N=10とする
  • P側は1~2で構成するとすると、Q側は1~5まで使える
  • P側は1~3で構成するとすると、Q側は1~3まで使える
  • そうやって足していけばいいように思えるが、上記2行には重複がある
    • P側=1,1,1,1,1,1,1,1,1,1 Q側=1,1,1,1,1,1,1,1,1,1 など
    • 重複なく数える必要がある
  • P側で1~3で構成するとして、310で考えると、3が含まれない数列も含まれる
    • 1~3で構成して、3が1つは含まれる数列はいくつだろう
    • 310 - 210 である
  • そのようにP側を分離すると、Q側が取れる場合の数も決まり、求まる
  • コードを書く前にN=3で答えが一致することを確認した (サンプル3)

f:id:peroon:20200511120603p:plain

code抜粋

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;
 
    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    mint sum = 0;
    
    FOR(i, 1, N+1){
      // P側の個数
      ll a = mod_pow(i, 10) - mod_pow(i-1, 10);
      if(a<0) a+=mod;

      // Q側の最大値
      ll b = N/i;
      ll c = mod_pow(b, 10);

      sum += a*c;
    }
    p(sum.x);
    
    return 0;
}