結果
問題 | No.546 オンリー・ワン |
ユーザー | sugarrr |
提出日時 | 2020-03-13 22:13:32 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,337 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 164,148 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 16:54:59 |
合計ジャッジ時間 | 2,895 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
//#include <bits/stdc++.h>#include "bits/stdc++.h"using namespace std;typedef long long ll;//#include "boost/multiprecision/cpp_int.hpp"//typedef boost::multiprecision::cpp_int ll;typedef long double dd;#define i_7 (ll)(1E9+7)//#define i_7 998244353#define i_5 i_7-2ll mod(ll a){ll c=a%i_7;if(c>=0)return c;return c+i_7;}typedef pair<ll,ll> l_l;typedef pair<dd,dd> d_d;ll inf=(ll)1E16;#define rep(i,l,r) for(ll i=l;i<=r;i++)#define pb push_backll max(ll a,ll b){if(a<b)return b;else return a;}ll min(ll a,ll b){if(a>b)return b;else return a;}void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);void Min(ll &pos,ll val){pos=min(pos,val);}void Add(ll &pos,ll val){pos=mod(pos+val);}dd EPS=1E-9;#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);#define fi first#define se second#define endl "\n"#define SORT(x) sort(x.begin(),x.end())#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())//template<class T>void max(T a,T b){if(a<b)return b;else return a;}//template<class T>void min(T a,T b){if(a>b)return b;else return a;}//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}//////////////////////////ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}ll lcm(ll a,ll b){return a*b/gcd(a,b);}ll n,l,h;ll a[15];void cal(ll &s1,ll t,ll i){ll g=1,c=0;rep(j,0,n-1){if(i&(1<<j)){c++;g=lcm(g,a[j]);if(g>1E9)return;}}if(c%2==1){s1+=t/g*c;}else{s1-=t/g*c;}}ll solve(ll t){ll s1=0;rep(i,1,(1<<n)-1){cal(s1,t,i);}return s1;}ll solve2(ll t){ll res=0;rep(i,1,t){ll c=0;rep(j,0,n-1){if(i%a[j]==0)c++;}if(c==1)res++;}return res;}int main(){fastiocin>>n>>l>>h;rep(i,0,n-1)cin>>a[i];/*solve(3);rep(x,1,20){cout<<x<<" "<<solve(x)<<endl;}*/cout<<solve(h)-solve(l-1)<<endl;return 0;}