Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2424-bb5ed0b6
この記事にトラックバックする(FC2ブログユーザー)

Round #209 DIV2 C問題 - Prime Number (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 C問題 (1500pt)
Problem description

問題概要

 $\displaystyle \frac{1}{x^{a_1}} + \frac{1}{x^{a_2}} + \ldots + \frac{1}{x^{a_n}} = \frac{s}{t},\ t = x^{a_1+a_2+\cdots +a_n}$
と書いた時,$s/t$ をいくら約分できるか,つまり,${\rm gcd}(s,t)\ {\rm mod}\ (10^9+7)$ を求める問題.
$1 \leq n \leq 10^5$
$2 \leq x \leq 10^9$
$0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^9$

解法

普通に通分すると,分母は $x^{a_n}$ なので,とりあえずそれを基準に考える.($x^{a_1+a_2+\cdots+a_{n-1}}$ では取り敢えず約分できる)
後は,$a_n$ と等しい要素の数 $D$ が,$x$ の倍数なら,もう $1$ 回 $x$ で約分できる.
更に,その時,$D/x + (a_n - 1$と等しい要素の数$)$ が $x$ の倍数なら,更にもう $1$ 回 $x$ で約分できる.
というのを繰り返していく.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007
void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

int main(){
  int n, x;
  static int in[1000000];
  ll res, cnt, now, dif, sum;
  int dame;

  int i, j;

  scanf("%d%d",&n,&x);
  n++; in[0]=0;
  REP(i,1,n) scanf("%d",in+i);
  intSort(in,n);

  res = sum = 0;
  rep(i,n) sum += in[i];
  res = sum - in[n-1];

  cnt = 0; now = in[n-1];
  for(i=n-1;i>=0;i--){
    if(in[i]==now){ cnt++; continue; }
    dif = now - in[i];
    dame = 0;
    for(;;){
      if(dif==0) break;
      if(cnt%x){ dame=1; break; }
      cnt /= x; dif--; res++;
    }
    if(dame) break;
    cnt++;
    now = in[i];
  }

  res = pw(x, res, M);
  printf("%d\n",(int)res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2424-bb5ed0b6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。