結果

問題 No.2589 Prepare Integers
コンテスト
ユーザー Newtech66
提出日時 2024-08-26 01:45:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,220 ms / 2,000 ms
コード長 5,479 bytes
コンパイル時間 3,727 ms
コンパイル使用メモリ 205,680 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-26 01:45:58
合計ジャッジ時間 13,154 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/istream:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/sstream:38,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/complex:45,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ccomplex:39,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:54,
                 from main.cpp:1:
In member function 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>]',
    inlined from 'void solve()' at main.cpp:180:19:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:202:25: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized]
  202 |       { return _M_insert(__n); }
      |                ~~~~~~~~~^~~~~
main.cpp: In function 'void solve()':
main.cpp:170:44: note: 'ans' was declared here
  170 |             lol l = 1, r = L.total(), mid, ans;
      |                                            ^~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int exgcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}


struct LinearBasis{
    static const int d = 61;
    int mod;
    struct Vector{
        int mod;
        vector<int> vec;
        Vector(int v, int m):mod(m){
            vec.resize(d, 0);
            vector<int> t;
            while(v){
                t.push_back(v % mod);
                v /= mod;
            }
            for(int i=0;i<(int)t.size();i++){
                vec[d-1-i] = t[i];
            }
        }
        int add(int a, int b){
            return a+b>=mod?a+b-mod:a+b;
        }
        int sub(int a, int b){
            return a>=b?a-b:a-b+mod;
        }
        lol to_number(){
            lol R = 0;
            for(int i=0;i<d;i++){
                R = mod * R + vec[i];
            }
            return R;
        }
        int operator[](int p){return vec[p];}
        const int operator[](int p) const{return vec[p];}
        Vector& operator+=(const Vector& other){
            for(int i=0;i<d;i++){
                if(other[i] == 0)   continue;
                this->vec[i] = add(this->vec[i], other[i]);
            }
            return *this;
        }
        friend Vector operator+(Vector lhs, const Vector& rhs){
            lhs += rhs;
            return lhs;
        }
        Vector& operator-=(const Vector& other){
            for(int i=0;i<d;i++){
                if(other[i] == 0)   continue;
                this->vec[i] = sub(this->vec[i], other[i]);
            }
            return *this;
        }
        friend Vector operator-(Vector lhs, const Vector& rhs){
            lhs -= rhs;
            return lhs;
        }
        Vector& operator*=(const lol& scalar){
            for(int i=0;i<d;i++){
                if(this->vec[i] == 0)   continue;
                this->vec[i] = (this->vec[i] * scalar) % mod;
            }
            return *this;
        }
        friend Vector operator*(Vector lhs, const lol& rhs){
            lhs *= rhs;
            return lhs;
        }
        friend Vector operator*(const lol& rhs, Vector lhs){
            lhs *= rhs;
            return lhs;
        }
    };
    vector<Vector> A;   //this is the basis
    Vector vec(int v){
        return Vector(v, mod);
    }
    LinearBasis(int m): mod(m){A.resize(d,vec(0));}
    void add(Vector V){
        for(int i=0;i<d;i++){
            if(V[i] != 0){
                if(A[i][i] == 0){
                    int s,t;
                    exgcd(V[i], mod, s, t);
                    s = (s % mod + mod) % mod;
                    t = (t % mod + mod) % mod;
                    A[i] = V * s;
                    V = V * (mod / A[i][i]);
                }else if(V[i] % A[i][i] == 0){
                    V -= A[i] * (V[i] / A[i][i]);
                }else{
                    int s, t;
                    auto W = A[i];
                    exgcd(V[i], W[i], s, t);
                    s = (s % mod + mod) % mod;
                    t = (t % mod + mod) % mod;
                    A[i] = V * s + W * t;
                    V -= A[i] * (V[i] / A[i][i]);
                    W -= A[i] * (W[i] / A[i][i]);
                    add(W);
                }
            }
        }
    }
    lol total(){
        lol B = 1;
        for(int i=0;i<d;i++){
            if(A[i][i]) B *= mod / A[i][i];
        }
        return B;
    }
    lol kth(lol k){
        lol B = total();
        if(k > B)   return -1;
        auto R = vec(0);
        for(int i=0;i<d;i++){
            if(!A[i][i])    continue;
            B /= mod / A[i][i];
            int l = min((k - 1) / B, (lol)mod / A[i][i] - 1);
            int q = (l - R[i] / A[i][i]) % (mod / A[i][i]);
            if(q < 0)   q += mod / A[i][i];
            k -= l * B;
            R += A[i] * q;
        }
        return R.to_number();
    }
};

void solve(){
    lol k;
    int q;
    cin>>k>>q;
    auto L = LinearBasis(k);
    while(q--){
        int t;
        lol x;
        cin>>t>>x;
        if(t==1){
            L.add(L.vec(x));
        }else if(t==2){
            cout<<L.kth(x)<<endl;
        }else{
            // You can find the kth smallest number
            lol l = 1, r = L.total(), mid, ans;
            while(l<=r){
                mid = l + (r - l) / 2;
                if(L.kth(mid) <= x){
                    l = mid + 1;
                    ans = mid;
                }else{
                    r = mid - 1;
                }
            }
            cout<<ans<<endl;
        }
    }
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
// cin>>_;
while(_--)
{
    solve();
}
return 0;
}
0