結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー |
👑 ![]() |
提出日時 | 2021-11-05 21:55:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,542 bytes |
コンパイル時間 | 2,406 ms |
コンパイル使用メモリ | 195,056 KB |
最終ジャッジ日時 | 2025-01-25 12:14:10 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | WA * 24 |
コンパイルメッセージ
main.cpp:22:20: warning: overflow in conversion from ‘double’ to ‘ll’ {aka ‘long long int’} changes value from ‘2.1e+19’ to ‘9223372036854775807’ [-Woverflow] 22 | const ll INF = 1e18+2e19; | ~~~~^~~~~ main.cpp: In function ‘int main()’: main.cpp:36:11: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf ("%lld",&N); | ~~~~~~^~~~~~~~~~~ main.cpp:40:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | scanf ("%lld",&A[i]); | ~~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#include <iostream>#include <limits>#include <numeric>#include <type_traits>#include <bitset>#include <map>#include <set>#include <unordered_map>#include <unordered_set>#include <queue>#include <list>using namespace std;#define rep(i,n,m) for(ll (i)=(n);(i)<(m);(i)++)#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)using ll = long long;const ll mod = 1000000007;const ll inf = 1000000000;const ll INF = 1e18+2e19;void pline(vector<ll> lis){rep(i,0,lis.size()){printf ("%lld",lis[i]);if (i != lis.size()-1) printf("\n");else printf("\n");}}int main(){ll N;scanf ("%lld",&N);vector<ll> A(N);rep(i,0,N){scanf ("%lld",&A[i]);}vector<ll> vdp(1000001 , 0);for (ll a : A){vdp[a] += 1;}rep(i,1,1000001){for (ll j = 2*i ; j < 1000001 ; j+=i){vdp[i] += vdp[j];}}vector<ll> rdp(N , 0);rep(i,0,1000001){if (vdp[i] != 0) rdp[ N-vdp[i] ] = i;}rep(i,1,N){rdp[i] = max(vdp[i] , vdp[i-1]);}pline(rdp);}/*消すのと同じ・・・?個取った時のGCDの最大値を求める。gcdを決め打った時、取れるのはgcdの倍数だけそれぞれの数字に関して、gcdとした時いくつ取れるか?を計算すればおkこれは、maxA log maxAvdp[v] = gcdをvとした時、とれる個数の最大値rdp[s] = s個取るとき、ありうるgcdの最大値とすればおk*/