結果

問題 No.546 オンリー・ワン
ユーザー rapurasurapurasu
提出日時 2017-07-15 15:07:42
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,552 bytes
コンパイル時間 1,350 ms
コンパイル使用メモリ 160,172 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-10-08 02:24:48
合計ジャッジ時間 4,727 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,636 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

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