結果
問題 | No.1409 Simple Math in yukicoder |
ユーザー |
![]() |
提出日時 | 2021-02-26 23:49:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,085 bytes |
コンパイル時間 | 703 ms |
コンパイル使用メモリ | 79,880 KB |
最終ジャッジ日時 | 2025-01-19 07:23:57 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef long long ll;ll pw(ll a,ll x,ll mod){ll ret = 1;while(x){if(x&1) (ret *= a) %= mod;(a *= a) %= mod; x /= 2;}return ret;}vector<int> di[100010] = {};int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);int t; cin >> t;for(int i=2;i<=100000;i++){for(int j=2*i;j<=100000;j+=i){di[j].push_back(i);}}while(t){t--;int i,j,x,v; cin >> v >> x;if(v*x==1){cout << 1 << endl;continue;}int r = -1,p = x*v + 1;for(i=2;i<=x*v;i++){bool f = true;for(int num: di[p - 1]){if(pw(i,num,p)==1) f = false;}if(f){r = i; break;}}vector<int> ans;for(i=1;i<=x;i++) ans.push_back(pw(r,i*v,p));sort(ans.begin(),ans.end());for(i=0;i<x;i++) cout << ans[i] << " ";cout << endl;}}