結果
問題 | No.546 オンリー・ワン |
ユーザー |
![]() |
提出日時 | 2018-11-29 17:55:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 987 bytes |
コンパイル時間 | 1,652 ms |
コンパイル使用メモリ | 196,968 KB |
最終ジャッジ日時 | 2025-01-06 17:46:02 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //INSERT ABOVE HERE signed main(){ Int n,l,h; cin>>n>>l>>h; vector<Int> c(n); for(Int i=0;i<n;i++) cin>>c[i]; const Int MAX = 1e9+100; auto lcm=[&](Int x,Int y){ if(max(x,y)>=MAX) return MAX; Int l=x/__gcd(x,y)*y; return min(MAX,l); }; auto calc= [&](Int x){ Int s=1<<n; vector<Int> dp(s); for(Int b=0;b<s;b++){ Int l=1; for(Int i=0;i<n;i++) if((b>>i)&1) l=lcm(l,c[i]); dp[b]=x/l; } for(Int i=0;i<n;i++) for(Int b=0;b<s;b++) if((~b>>i)&1) dp[b]-=dp[b|(1<<i)]; Int res=0; for(Int i=0;i<n;i++) res+=dp[1<<i]; return res; }; cout<<calc(h)-calc(l-1)<<endl; return 0; }