結果
問題 |
No.3276 Make Smaller Popcount
|
ユーザー |
|
提出日時 | 2025-10-10 14:17:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 424 ms / 2,000 ms |
コード長 | 4,338 bytes |
コンパイル時間 | 5,751 ms |
コンパイル使用メモリ | 335,380 KB |
実行使用メモリ | 9,616 KB |
最終ジャッジ日時 | 2025-10-10 14:17:41 |
合計ジャッジ時間 | 23,974 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
//#define //_GLIBCXX_DEBUG #include <bits/stdc++.h> #include <deque> #include <atcoder/all> #pragma GCC optimize("03") using namespace std; using namespace atcoder; using mint = atcoder::modint1000000007; using ll = long long; using ull = unsigned long long; using vll=vector<ll>; using vvll=vector<vector<ll>>; using vvvll=vector<vvll>; using vvvvll=vector<vvvll>; using Graph=vvll; using Edgegraph=vector<vector<pair<ll,ll>>>; using vch=vector<char>; using vvch=vector<vector<char>>; using P=pair<ll,ll>; using vP=vector<P>; using tup=tuple<ll,ll,ll>; using vbl=vector<bool>; using vvbl=vector<vbl>; using vs=vector<string>; using vvs=vector<vs>; using vd=vector<double>; using vvd=vector<vd>; using vvld=vector<vector<long double>>; const int infint = 1073741823; const ll inf = 1LL << 60; template <class T> inline bool chmax(T& a,T b){if (a<b){a=b;return 1;}return 0;} template <class T> inline bool chmin(T& a,T b){if (a>b){a=b;return 1;}return 0;} #define rep(i,x,lim) for(ll i = (x);i < (ll)(lim);i++) #define rep2(j,x,lim) for(int j = (x);j < (int)(lim);j++) const ll big=(1e+9)+7; const ll big2=998244353; ll dx[8]={1,-1,0,0,1,1,-1,-1}; ll dy[8]={0,0,1,-1,1,-1,1,-1}; int modpow(ll x,ll n,ll m){ if(n==0) return 1%m; x=((x%m)+m)%m; if(n%2==0){ ll r=modpow(x,n/2,m); return r*r%m; } else{ ll r=modpow(x,n/2,m); return r*r%m*x%m; } } //pは素数でなければならない。 int revmod(ll x,ll p){return modpow(x,p-2,p);} //99 のRを高速に求める int modp(ll p,ll q){ ll gc=gcd(p,q); p/=gc;q/=gc; ll rev=revmod(p,big2); return (rev*q)%big2; } //nCrを求める modbig2 int nCr(ll n,ll r){ ll ans=1; rep(i,1,n+1) ans=(ans*i)%big2; rep(i,1,r+1) ans=(ans*modpow(i,big2-2,big2))%big2; rep(i,1,n-r+1) ans=(ans*modpow(i,big2-2,big2))%big2; return ans; } #include <iostream> using namespace std; // AtCoder の modint を使う const int MAX = 510000; mint fac[MAX], finv[MAX], inv[MAX]; void COMinit() { const int MOD = mint::mod(); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i; inv[i] = MOD - inv[MOD%i] * (MOD / i); finv[i] = finv[i - 1] * inv[i]; } } // 二項係数計算 mint COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * finv[k] * finv[n - k]; } inline long long mod(long long a, long long m) { return (a % m + m) % m; } long long extGcd(long long a, long long b, long long &p, long long &q) { if (b == 0) { p = 1; q = 0; return a; } long long d = extGcd(b, a%b, q, p); q -= a/b * p; return d; } // 中国剰余定理 // リターン値を (r, m) とすると解は x ≡ r (mod. m) // 解なしの場合は (0, -1) をリターン pair<long long, long long> ChineseRem(const vector<long long> &b, const vector<long long> &m) { long long r = 0, M = 1; for (int i = 0; i < (int)b.size(); ++i) { long long p, q; long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d) if ((b[i] - r) % d != 0) return make_pair(0, -1); long long tmp = (b[i] - r) / d * p % (m[i]/d); r += M * tmp; M *= m[i]/d; } return make_pair(mod(r, M), M); } // 入力:n <= 4.5*10^18, nは平方数 int64_t isqrt(int64_t n) { // 4.5*10^18 < 2^62 // 真の答えは 2 <= _ < 2^31 の範囲にある int64_t low = 0, high = 1LL<<30; while (low < high-1) { int64_t mid = (low + high) / 2; int64_t mid2 = mid * mid; // 最初の上界を2^31程度に抑えているのでここではオーバーフローしない if (mid2 < n) { low = mid; } else if (mid2 == n) { return mid; } else { high = mid; } } return low; } using S=array<mint,3>; S e(){return S();} S op(S x,S y){return {x[0]+y[0],x[1]+y[1],x[2]+y[2]};} int main(){ ll T; cin >> T; while(T--){ ll N; cin >> N; ll first=inf; ll second=inf; for(ll i=0;i<=29;i++){ if(N >> i & 1){ if(first==inf) first=(1 << i); else if(second==inf) second=(1<< i); } } if(second!=inf) cout << second-first << '\n'; else cout << -1 << '\n'; } }