結果

問題 No.917 Make One With GCD
ユーザー ibylog
提出日時 2021-01-22 19:46:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,448 bytes
コンパイル時間 2,322 ms
コンパイル使用メモリ 202,128 KB
最終ジャッジ日時 2025-01-18 03:31:05
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 17 WA * 6 TLE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:31:17: warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.0e+18’ to ‘2147483647’ [-Woverflow]
   31 | const int INF = 1e18;
      |                 ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
////////////////////////
#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