結果
問題 |
No.1871 divisXor
|
ユーザー |
|
提出日時 | 2025-03-18 19:35:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,663 bytes |
コンパイル時間 | 2,428 ms |
コンパイル使用メモリ | 205,512 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-18 19:35:28 |
合計ジャッジ時間 | 7,714 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | WA * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; // Function to compute sum of divisors for numbers up to LIMIT vector<int> computeSumOfDivisors(int LIMIT) { vector<int> sumDiv(LIMIT + 1, 1); for (int i = 2; i <= LIMIT; i++) { for (int j = i; j <= LIMIT; j += i) { sumDiv[j] += i; } } return sumDiv; } // Function to find a subset of numbers whose sum of divisors XORs to N bool findSubset(int N, const vector<int>& sumDiv, vector<int>& result) { vector<pair<int, int>> values; // Store (sum of divisors, number) for (int i = 1; i < sumDiv.size(); i++) { values.emplace_back(sumDiv[i], i); } sort(values.begin(), values.end()); // Sort to prioritize smaller numbers int max_size = values.size(); for (int mask = 1; mask < (1 << max_size); mask++) { // Try all subsets int xor_sum = 0; vector<int> temp_result; for (int i = 0; i < max_size; i++) { if (mask & (1 << i)) { xor_sum ^= values[i].first; temp_result.push_back(values[i].second); } } if (xor_sum == N) { result = temp_result; return true; } } return false; } int main() { int N; cin >> N; if (N == 0) { cout << "-1\n"; return 0; } int LIMIT = 1000; vector<int> sumDiv = computeSumOfDivisors(LIMIT); vector<int> result; if (findSubset(N, sumDiv, result)) { cout << result.size() << "\n"; for (int num : result) cout << num << " "; cout << "\n"; } else { cout << "-1\n"; } return 0; }