結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー rapurasu
提出日時 2017-07-15 15:09:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,554 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 167,080 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-08 02:25:14
合計ジャッジ時間 2,617 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
LL L,H;
LL C[20];
LL kaizyou(LL N,LL x){
   LL ans=1;
   REP(i,x){
       ans*=(N-i);
       ans/=(i+1);
   }
   return ans;
}
LL d[20];
void init(){
   d[0]=0;
   d[1]=1;
   d[2]=-2;
   for(int i=2;i<11;i++){
       LL now=0;
       for(int j=1;j<i;j++){
           //if(j%2==0){
              //now+=kaizyou(i,j)*d[j];
           //}else{
              now-=kaizyou(i,j)*d[j];
           //}
       }
       d[i]=now;
       //cout<<d[i]<<endl;
   }
}


LL gcd(LL a,LL b){
   //if(a<b)return gcd(b,a);
   if(b==0)return a;
   return gcd(b,a%b);
}

LL houzyo(LL x){
   LL ans=0;
   REP(i,1<<N){
       LL now=1;
       int count=0;
       REP(j,N){
           if((i>>j)&1){
              count++;
              LL a=gcd(now,C[j]);
              now=(now*C[j])/a;
           }
       }
       //cout<<now<<endl;
       //if(count>2)continue;
       /*if(count%2==0){
          if(count==0)continue;
          ans-=(x/now);
       }else{
          if(count!=1){
             ans+=(x/now);
          }else{
             ans+=(x/now);
          }
       }*/
       ans+=d[count]*(x/now);
       //cout<<ans<<endl;
   }
   return ans;
}

int main(){
    cin>>N>>L>>H;
    REP(i,N){
        cin>>C[i];
    }
    init();
   // cout<<houzyo(H)<<endl;
    cout<<houzyo(H)-houzyo(L-1)<<endl;;
    return(0);
}
0