結果
問題 | No.546 オンリー・ワン |
ユーザー | rapurasu |
提出日時 | 2017-07-15 15:09:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 3 ms
6,816 KB |
testcase_09 | AC | 3 ms
6,816 KB |
testcase_10 | AC | 4 ms
6,816 KB |
ソースコード
#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); }