結果
| 問題 | No.1926 Sequence of Remainders |
| ユーザー |
 CKyopro
|
| 提出日時 | 2022-05-06 22:10:07 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 295 ms / 2,000 ms |
| コード長 | 25,237 bytes |
| コンパイル時間 | 6,266 ms |
| コンパイル使用メモリ | 417,404 KB |
| 最終ジャッジ日時 | 2025-01-29 03:32:00 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 35 |
ソースコード
#include <iostream>#include <map>#include <set>#include <climits>#include <queue>#include <bitset>#include <sstream>#include <deque>#include <cassert>#include <functional>/*#if __has_include(<atcoder/modint>)# include <atcoder/modint># include <atcoder/segtree># include <atcoder/dsu># include <atcoder/math># include <atcoder/scc>#endif*/#if __has_include(<atcoder/all>)#include <atcoder/all>#endif#include <unordered_map>#include <unordered_set>#include <cmath>#include <numeric>#include <iomanip>#include <algorithm>#include <stack>#include <ios>#include <iomanip>#include <cstdio>#if __has_include( <boost/integer/extended_euclidean.hpp>)# include <boost/multiprecision/cpp_int.hpp># include<boost/integer/extended_euclidean.hpp>#endif#define CLiBCXX_DEBUG#define ll long long#define ull unsigned long long#define hmap unordered_map#define hset unordered_setusing namespace std;#if __has_include(<atcoder/modint>)using namespace atcoder;using mint10 = static_modint<10>;using mint24 = static_modint<24>;using mint3 = static_modint<3>;using minta = modint998244353;using mintb = modint1000000007;#endifll powll(ll a, ll b){return (ll)pow(a, b / 2) * (ll)pow(a, b - b / 2);}ll sum(ll a, ll b){return a + b;}ll e(){return 0;}//see abc126 bll lis(vector<ll> v){ll dp[200300];ll sz = v.size();for(ll i = 0; i < sz; ++i){dp[i]=LLONG_MAX;}auto itr = v.begin();auto len = 1;dp[0]=*itr;++itr;for(;itr != v.end();++itr){ll val = *itr;ll l = -1;ll r = len;while(r - l!=1){ll piv = (l+r)/2;if(dp[piv]>=val){r = piv;}else{l = piv;}}if(dp[r]==LLONG_MAX){len++;}dp[r]=val;}return len;}//return true if an argument is prime or one#if __has_include( <boost/integer/extended_euclidean.hpp>)bool isPrime(double num, set<ll>& primes, set<ll>& comps){if(num==1){return false;}if(primes.find(num)!=primes.end()){return true;}if(comps.find(num)!=comps.end()){return false;}double sq = sqrtf64(num);for(int32_t i = 2; i <= sq; ++i){if((ll)num%i==0){comps.insert(num);return false;}}primes.insert(num);return true;}#endif//up to 3000 charactorsstring LCS(string s, string t){ll ss = s.size();ll ts = t.size();ll **a = new ll*[3001];for(ll i = 0; i < 3001; ++i) a[i]= new ll[3001];for(ll i = 0; i < 3001; ++i){a[i][0]=0;}for(ll j = 0; j < 3001; ++j){a[0][j]=0;}for(ll i = 1; i <= ss; ++i){for(ll j = 1; j <= ts; ++j){if(s[i-1]==t[j-1]){a[i][j]=a[i-1][j-1]+1;}else{a[i][j]=max(a[i-1][j],a[i][j-1]);}}}//cout << a[ss][ts]<<endl; // testvector<char> rans;ll i_r = ss;ll j_r = ts;while(a[i_r][j_r]!=0){if(s[i_r-1]==t[j_r-1]){rans.push_back(s[i_r-1]);i_r--;j_r--;}else{if(a[i_r][j_r]==a[i_r-1][j_r]){i_r--;}else{j_r--;}}}stringstream sst;for(auto i = rans.rbegin(); i != rans.rend(); ++i){sst << *i;}for(ll i = 0; i < 3001; ++i) delete[] a[i];delete[] a;return sst.str();}ll zeroll(){return 0;}#if __has_include(<atcoder/modint>)ll count_inversion(vector<ll> v){ll n = v.size();segtree<ll, sum,zeroll> seg(n);ll c = 0;for(ll i = 0; i < n; ++i){ll tmpa=v[i];tmpa--;c+=seg.prod(tmpa,n);seg.set(tmpa,1);}return c;}#endif//TODO パッケージ化/*ll root(ll v,vector<ll>& parents){assert(parents.size()>v&&v>=0);if(parents[v]==v){return v;}return parents[v]=root(parents[v], parents);}//最小全域木vector<vector<ll>> MST(vector<ll> starts, vector<ll> ends, vector<ll> costs, ll n){assert(starts.size()==ends.size());assert(starts.size()==costs.size());ll m = starts.size();for(ll i = 0; i < m; ++i){assert(starts[i]!=ends[i]);}set<ll> added;auto more = [](pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b){return a.first>b.first;};priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,decltype(more)> pq(more);for(ll i = 0; i < m; ++i){pq.push(make_pair(costs[i],make_pair(starts[i],ends[i])));}vector<ll> tmpv;vector<vector<ll>> ans(n,tmpv);vector<ll> parents(n);for(ll i = 0; i < n; ++i){parents[i]=i;}vector<ll> tree_size(n,1);auto marge_sec = [](ll a, ll b, vector<ll>& parents, vector<ll>& tree_size){assert(a!=b);tree_size[root(a, parents)]+=tree_size[root(b, parents)];parents[root(b,parents)]=root(a, parents);};ll total_cost = 0;while(tree_size[parents[0]]!=n&&!pq.empty()){auto current = pq.top();auto cost = current.first;auto edge = current.second;ll a = edge.first;ll b = edge.second;pq.pop();if(root(a,parents)==root(b,parents)){//skip because it makes a cycle}else{marge_sec(a,b,parents,tree_size);ans[a].push_back(b);total_cost+=cost;}}return ans;}//最小全域木のコスト合計ll MSTCost(vector<ll> starts, vector<ll> ends, vector<ll> costs, ll n){assert(starts.size()==ends.size());assert(starts.size()==costs.size());ll m = starts.size();for(ll i = 0; i < m; ++i){assert(starts[i]!=ends[i]);}set<ll> added;auto more = [](pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b){return a.first>b.first;};priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,decltype(more)> pq(more);for(ll i = 0; i < m; ++i){pq.push(make_pair(costs[i],make_pair(starts[i],ends[i])));}vector<ll> tmpv;vector<vector<ll>> ans(n,tmpv);vector<ll> parents(n);for(ll i = 0; i < n; ++i){parents[i]=i;}vector<ll> tree_size(n,1);auto marge_sec = [](ll a, ll b, vector<ll>& parents, vector<ll>& tree_size){assert(a!=b);tree_size[root(a, parents)]+=tree_size[root(b, parents)];parents[root(b,parents)]=root(a, parents);};ll total_cost = 0;while(tree_size[parents[0]]!=n&&!pq.empty()){auto current = pq.top();auto cost = current.first;auto edge = current.second;ll a = edge.first;ll b = edge.second;pq.pop();if(root(a,parents)==root(b,parents)){//skip because it makes a cycle}else{marge_sec(a,b,parents,tree_size);ans[a].push_back(b);total_cost+=cost;}}return total_cost;}*/#if __has_include(<atcoder/all>)//二点間最短経路 大体O((N+M)logM)ll shortestPathDistance(ll size, vector<ll> froms, vector<ll> tos, vector<ll> costs, int start, int end){assert(froms.size()==tos.size());assert(froms.size()==costs.size());mcf_graph<int,ll> g(size);for(ll i = 0; i < froms.size(); ++i){g.add_edge(froms[i],tos[i],1,costs[i]);}auto p = g.flow(start,end);return (p.first!=0?p.second:LLONG_MAX);}//二点間最短経路 コストが1の場合ll shortestPathDistance(ll size, vector<ll> froms, vector<ll> tos, int start, int end){assert(froms.size()==tos.size());vector<ll> costs;for(ll i = 0; i < froms.size(); ++i){costs.push_back(1);}return shortestPathDistance(size,froms,tos,costs,start,end);}#endif//ダイクストラ 始点固定vector<ll> shortestPathDistances(ll size, vector<vector<pair<ll,ll>>> edges, ll start){#define iNF LLONG_MAX/3vector<ll> ans(size,iNF);ans[start] = 0;priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> nexts;nexts.push(make_pair(0,start));vector<ll> determined(size,false);while(!nexts.empty()){ll idx = nexts.top().second;ll cost = nexts.top().first;nexts.pop();if(determined[idx]){continue;}determined[idx]=true;for(ll i = 0; i < edges[idx].size(); ++i){if(!determined[edges[idx][i].first]){if(ans[edges[idx][i].first]>ans[idx]+edges[idx][i].second){nexts.push(make_pair(ans[idx]+edges[idx][i].second,edges[idx][i].first));ans[edges[idx][i].first]=ans[idx]+edges[idx][i].second;}}}}return ans;}//葉が始点群、根が終点template<class Score>class TreeDP{private:vector<Score> score;function<Score (Score, Score)> op;vector<vector<int>> edges;int size;public:TreeDP(int n, Score def, function<Score (Score, Score)> op){vector<int> score(n,def);this.score=score;this.op = op;this.size = n;}void add_edge(int a, int b){edges[a].push_back(b);}vector<Score> prod(){vector<int> in(size,0);//入向辺for(int i = 0; i < edges.size(); ++i){for(int j = 0; j < edges[i].size(); ++j){in[edges[i][j]]++;}}queue<int> no_in;for(int i = 0; i < in.size(); ++i){if(in[i]==0){no_in.push(i);}}vector<int> sorted;while(!no_in.empty()){int curr = no_in.front();sorted.push_back(curr);no_in.pop();for(ll i = 0; i < edges[curr].size(); ++i){int to = edges[curr][i];in[to]--;if(in[to]==0){no_in.push(to);}}}for(int i = 0; i < sorted.size(); ++i){for(int j = 0; j < edges[sorted[i]].size(); ++j){int to = edges[sorted[i]][j];int from = i;score[to]=op(score[to],score[from]);}}return score;}};namespace cell{//Union-Findclass uf{public:uf(ll n){par.resize(n);sizes.resize(n);for(ll i = 0; i < n; ++i){par[i]=i;sizes[i]=1;}}void merge(ll a, ll b){sizes[root(a)]+=sizes[root(b)];par[root(b)]=root(a);}vector<ll> par;vector<ll> sizes;ll root(ll a){if(par[a]==a){return a;}else{return par[a]=root(par[a]);}}ll size(ll a){return sizes[root(a)];}bool same(ll a, ll b){if(root(a)==root(b)){return true;}else{return false;}}};class modint998244353{public:ll m = 998244353;ll value;modint998244353(ll a){value = (a+m*10)%m;}modint998244353 operator*(modint998244353 b){return modint998244353((this->value*b.value+m)%m);}modint998244353 pow(ll b){if(b==1){return *this;}else if(b==0){return 1;}if(b%2==1){return pow(b-1)**this;}else{modint998244353 co = pow(b/2);return co*co;}}modint998244353 operator/(modint998244353 b){if(b.value==1){return *this;}return *this*b.pow(m-2);}modint998244353 operator+(modint998244353 b){return this->value+b.value;}modint998244353 operator-(modint998244353 b){return this->value-b.value;}};class modint1000000007{public:ll m = 998244353;ll value;modint1000000007(ll a){value = (a+m*10)%m;}modint1000000007 operator*(modint1000000007 b){return modint1000000007((this->value*b.value+m)%m);}modint1000000007 pow(ll b){if(b==1){return *this;}else if(b==0){return 1;}if(b%2==1){return pow(b-1)**this;}else{modint1000000007 co = pow(b/2);return co*co;}}modint1000000007 operator/(modint1000000007 b){if(b.value==1){return *this;}return *this*b.pow(m-2);}modint1000000007 operator+(modint1000000007 b){return this->value+b.value;}modint1000000007 operator-(modint1000000007 b){return this->value-b.value;}};//強連結成分分解class scc_graph{public:ll ns;//sizescc_graph(ll n){ns=n;vector<vector<ll>> vn(ns);v = vn;rv = vn;}void add_edge(int s, int t){assert(0<=s);assert(s<ns);assert(0<=t);assert(t<ns);v[s].push_back(t);rv[t].push_back(s);}vector<vector<ll>> scc(){dfsVec.resize(0);checked.assign(ns,false);for(ll i = 0; i < ns; ++i){dfs(i);}vector<vector<ll>> ans;ll m = dfsVec.size();checked.assign(ns,false);for(ll i = m-1; i>=0; --i){ll el = dfsVec[i];rdfsVec.resize(0);if(checked[el]){continue;}rdfs(el);ans.push_back(rdfsVec);}return ans;}protected:vector<ll> dfsVec;vector<ll> rdfsVec;void dfs(ll i){if(checked[i]){return;}checked[i]=true;auto elist = v[i];for(ll j = 0; j < elist.size(); ++j){dfs(elist[j]);}dfsVec.push_back(i);}void rdfs(ll i){if(checked[i]){return;}checked[i]=true;auto elist = rv[i];for(ll j = 0; j < elist.size(); ++j){rdfs(elist[j]);}rdfsVec.push_back(i);}vector<bool> checked;vector<vector<ll>> v;vector<vector<ll>> rv;};//セグメントツリーtemplate<class S>class segtree{public:segtree(S n, function<S(S,S)> op, function<S()> e){this->op=op;this->e=e;ns = n;S default_val = e();val_con.assign(ns*2,default_val);}void set(ll p, S x){ll idx = p + ns;val_con[idx]=x;while(idx>0){idx = ((idx+1)/2)-1;ll l = (idx+1)*2-1;ll r = (idx+1)*2;val_con[idx]=op(val_con[l],val_con[r]);}val_con[0]=op(val_con[1],val_con[2]);}S get(ll p){ll idx = p + ns;return val_con[idx];}S prod(ll l, ll r){ll idx = l;S ans = e();while(idx<r){ll size = 1;ll raw_idx = idx+ns;while(idx+size*2-1<r&&raw_idx>0&&(raw_idx+1)%2==0){size*=2;raw_idx=((raw_idx+1)/2-1);}ans = op(ans,val_con[raw_idx]);idx+=size;}return ans;}protected:ll ns;vector<S> val_con;function<S(S,S)> op;function<S()> e;};//2次元UnionFindclass squf:cell::uf{public:squf(ll n):cell::uf(n*n){sz=n;}void merge(ll a1, ll a2, ll b1, ll b2){cell::uf::merge(a1*sz+a2,b1*sz+b2);}bool same(ll a1, ll a2, ll b1, ll b2){return cell::uf::same(a1*sz+a2,b1*sz+b2);}protected:ll sz;};//最短経路(ダイクストラ)class sp_graph{public:sp_graph(ll n){ns = n;w.assign(n,inf);seen.assign(n,false);calculated=false;vector<pair<ll,ll>> b;seen_cnt=0;edges.assign(n,b);queued.assign(n,false);sources.resize(0);}void add_edge(ll a, ll b, ll cost){assert(0<=a&&a<ns);assert(0<=b&&b<ns);assert(0<=cost);edges[a].push_back(make_pair(b,cost));}void set_seen(ll n){seen[n]=true;}void set_seen(function<bool(ll)> if_set){for(ll i = 0; i < ns; ++i){if(if_set(i)){set_seen(i);}}}void set_seen(function<bool(ll,void*)> if_set, void* ptr){for(ll i = 0; i < ns; ++i){if(if_set(i, ptr)){set_seen(i);}}}//最短経路上の重みの総和を返します。経路が存在しない場合はLLONG_MAXと等しい値を返します。ll sp(ll a, ll b){assert(0<=a&&a<ns);assert(0<=b&&b<ns);if(calculated&&start_node==a){return w[b];}reset();start_node=a;end_node=b;calculated=true;//bfsで到達不能な場所を数えるvector<bool> bfs_reachable(ns,false);bfs(edges,bfs_reachable,a);ll reachables = 0;for(ll i = 0; i < ns; ++i){if(bfs_reachable[i]){reachables++;}}//bfs終了queued_cost.assign(ns,LLONG_MAX);sources.assign(ns,-1);priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;//pair<score,index>priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> dets;//pair<score,index>pq.push(make_pair(0,a));dets.push(make_pair(0,-1));while(!pq.empty()){auto f = pq.top();auto source = dets.top().second;pq.pop();dets.pop();ll score = f.first;ll idx = f.second;if(seen[idx]){continue;}seen[idx]=true;sources[idx]=source;w[idx]=score;seen_cnt++;if(seen_cnt==reachables){break;}auto list = edges[idx];for(ll i = 0; i < list.size();++i){ll d = list[i].first;ll edge_cost = list[i].second;if(seen[d]){continue;}queued[d]=true;if(score+edge_cost<queued_cost[d]){queued_cost[d]=score+edge_cost;pq.push(make_pair(score+edge_cost,d));dets.push(make_pair(score+edge_cost,idx));}}}return w[b];}vector<ll> path(){assert(calculated);vector<ll> rans(0);ll b = end_node;ll a = start_node;while(true){if(b==-1){return vector<ll>(0);}else if(a==b){rans.push_back(b);break;}else{rans.push_back(b);b=sources[b];}}vector<ll> ans(rans.size());for(ll i = 0; i < rans.size(); ++i){ans[i]=rans[rans.size()-i-1];}assert(ans[0]==start_node);return ans;}vector<ll> get_sources(){return sources;}protected:void reset(){calculated=false;seen.assign(ns,false);w.assign(ns,inf);seen_cnt=0;queued.assign(ns,false);}void bfs(vector<vector<pair<ll,ll>>>& edges, vector<bool>& bfs_reachable, ll a){assert(0<=a&&a<=ns);if(bfs_reachable[a]){return;}bfs_reachable[a]=true;for(ll i = 0; i < edges[a].size(); ++i){bfs(edges,bfs_reachable,edges[a][i].first);}return;}const ll inf=LLONG_MAX;ll ns;vector<ll> w;vector<bool> seen;vector<bool> queued;vector<ll> queued_cost;ll seen_cnt;ll start_node;ll end_node;vector<vector<pair<ll,ll>>> edges;bool calculated;vector<ll> sources;};class grid_sp:cell::sp_graph{public:grid_sp(ll r, ll c):cell::sp_graph(r*c){rs=r;cs=c;}void add_edge(ll x1, ll y1, ll x2, ll y2, ll cost){cell::sp_graph::add_edge(x1*cs+y1,x2*cs+y2,cost);return;}void set_seen(ll x, ll y){cell::sp_graph::set_seen(x*cs+y);return;}void set_seen(function<bool(ll,ll)> if_set){for(ll i = 0; i < rs; ++i){for(ll j = 0; j < cs; ++j){if(if_set(i,j)){set_seen(i,j);}}}}void set_seen(function<bool(ll,ll, void*)> if_set, void* ptr){for(ll i = 0; i < rs; ++i){for(ll j = 0; j < cs; ++j){if(if_set(i,j,ptr)){set_seen(i,j);}}}}ll sp(ll x1, ll y1, ll x2, ll y2){ll a = x1*cs+y1;ll b = x2*cs+y2;return cell::sp_graph::sp(a,b);}protected:ll rs;ll cs;};}struct grid_ex_sp{ll h,w,p;char* grid;ll size;grid_ex_sp(ll H, ll W, ll P, char* GRID){grid = GRID;h = H;w = W;p = P;calc=false;size = h*w*p;}bool calc;void sp(ll r,ll c, ll re, ll ce){scores.assign(size,LLONG_MAX);priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;for(ll i = 0; i < p; ++i){pq.emplace(0,idx(r,c,i));}while(!pq.empty()){auto tp = pq.top();ll score = tp.first;ll curr = tp.second;pq.pop();ll cur_r,cur_c,cur_p;tie(cur_r,cur_c,cur_p)=locs(curr);}}vector<ll> scores;ll idx(ll r, ll c, ll pat){return r*w+c+h*w*pat;}ll up(ll idx){if(idx==-1){return -1;}auto loc = locs(idx);if(get<0>(loc)>0){return idx-w;}return -1;}ll down(ll idx){if(idx==-1){return -1;}auto loc = locs(idx);if(get<0>(loc)<h-1){return idx+w;}return -1;}ll left(ll idx){if(idx==-1){return -1;}auto loc = locs(idx);if(get<1>(loc)>0){return idx-1;}return -1;}ll right(ll idx){if(idx==-1){return -1;}auto loc = locs(idx);if(get<1>(loc)<w-1){return idx+1;}return -1;}tuple<ll,ll,ll> locs(ll idx){return make_tuple(idx%(h*w)/w,idx%w,idx/h*w);}bool valid(ll r,ll c, ll pat){if(0<=r&&r<h&&0<=c&&c<w&&0<pat&&pat<p){return true;}return false;}};//using bint = boost::multiprecision::cpp_int;int main(){ll t;cin >> t;for(ll i = 0 ;i < t; ++i){ll n,m,k;cin >> n >> m >> k;if(m-n<=k%m){cout << 0 <<endl;} else if(m-n==1){cout << 0 << endl;}else{cout << k%m << endl;}}}