結果

問題 No.917 Make One With GCD
ユーザー ibylogibylog
提出日時 2021-01-22 19:43:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,471 bytes
コンパイル時間 2,554 ms
コンパイル使用メモリ 212,844 KB
実行使用メモリ 16,960 KB
最終ジャッジ日時 2024-06-08 11:22:23
合計ジャッジ時間 9,165 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
////////////////////////
#define int long long
#define endl "\n"
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define ALL(a) a.begin(),a.end()
#define each(e,v) for(auto& e : v)
#define print(a) cout << (a) << endl
#define elif else if
#define len(X) ((int)(X).size())
using namespace std;
template<class T = int> using P = pair<T,T>;
template<class T = int> using Array = vector<T>;
template<class T = int> using Matrix = Array< Array<T> >;
template<class T> using heapq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using heapQ = priority_queue<T, vector<T>, greater<T>>;
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T> ostream& operator << (ostream &s, vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> &P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << ">"; } return s; }
template <class T>bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template <class T>bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}
template <class T = int>T gcd(T a, T b){return (b == 0) ? a : gcd(b, a % b);}
template <class T = int>T lcm(T a, T b){return a / gcd(a, b) * b;}
template <class T = int>T extgcd(T a,T b,T &x,T &y){T g = a;x = 1;y = 0;if (b != 0) {g = extgcd(b, a % b, y, x), y -= (a / b) * x;}return g;}
template<class T = int> T invMod(T a,T m){T x,y;if (extgcd(a, m, x, y) == 1) {return (x + m) % m;}else{return -1;}}
const int INF = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = 3.14159265358979323846;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
//////////////////////////////////



signed main(){
int n;cin>>n;Array<int> a(n);rep(i,n){cin>>a[i];}
map<int,int> X,Y;
rep1(i,(1<<(n/2)) - 1){
    int G = 0;
    rep(j,n/2){if((i>> j)&1){G = gcd(G,a[j]);}}
    X[G]++;}
reverse(ALL(a));
rep1(i,(1<<(n - n/2))-1){
    int G = 0;
    rep(j,n - n/2){if((i>> j)&1){G = gcd(G,a[j]);}}
    Y[G] ++;
}
  X[0] ++;Y[0]++;
int ans = 0;
    for(auto [u,v]:X)for(auto[x,y]:Y){
        if (gcd(u,x) == 1){ans += v*y;}
    }
    print(ans);
    return 0;
}
0