結果
問題 | No.1409 Simple Math in yukicoder |
ユーザー |
![]() |
提出日時 | 2021-02-26 22:59:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,736 bytes |
コンパイル時間 | 2,053 ms |
コンパイル使用メモリ | 175,572 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-02 15:47:12 |
合計ジャッジ時間 | 28,938 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
コンパイルメッセージ
main.cpp: In function 'int genshikon(int)': main.cpp:43:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 43 | for (auto [q,_] : v) { | ^
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2021.02.26 22:53:12**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template<typename T>vector<pair<T,int>> prime_factorization(T n) {vector<pair<T, int>> res;for (T i = 2; i*i <= n; i++) {int cnt = 0;while (n % i == 0) {n /= i;cnt++;}if (cnt > 0) res.push_back({i,cnt});}if (n > 1) res.push_back({n,1});return res;}ll powMod(ll k, ll n, ll mod) {ll x = 1;while (n > 0) {if (n & 1) {x = x * k % mod;}k = k * k % mod;n >>= 1;}return x;}int genshikon(int p) {auto v = prime_factorization(p-1);while(true) {int a = rand() % (p-2) + 1;for (auto [q,_] : v) {if (powMod(a,(p-1)/q,p) == 1) {a = -1;break;}}if (a == -1) continue;return a;}}int main() {int t;cin >> t;while(t--) {int v,x;cin >> v >> x;if (v == 1 && x == 2) {cout << 1 << " " << 2 << endl;continue;}else if (v == 2 && x == 1) {cout << 1 << endl;continue;}else if (v == 1 && x == 1) {cout << 1 << endl;continue;}int g = genshikon(x*v+1);vector<int> ans;for (int i = 0; i < x; i++) {ans.push_back(powMod(g,i*v,x*v+1));}sort(ans.begin(), ans.end());for (int i = 0; i < x; i++) {cout << ans[i] << " ";}cout << endl;}return 0;}