#733095 (C++17) No.1819 Mirrored 2

• 問題: No.1819 Mirrored 2
• ユーザー: Nachia
• 提出日時: 2022-01-21 22:51:01
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,795 bytes
• コンパイル時間: 973 ms
• コンパイル使用メモリ: 76,948 KB
• 最終ジャッジ日時: 2025-01-27 14:16:51
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 10 TLE * 16

ソースコード

#include <vector>
#include <utility>

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;

    StaticModint() : x(0){}
    StaticModint(unsigned int v) : x(v){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r){ auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r){ auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1) res *= a; a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return pow(MOD-2); }
    unsigned int val() const { return x; }
    static unsigned int get_mod() { return MOD; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

}


namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) {
        unsigned long long res = 1, aa = a;
        while(i){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
            i /= 2;
        }
        return res;
    }
    static constexpr bool examine_val(unsigned int g){
        unsigned int t = MOD - 1;
        for(unsigned long long d=2; d*d<=t; d++) if(t % d == 0){
            if(powm(g, (MOD - 1) / d) == 1) return false;
            while(t % d == 0) t /= d;
        }
        if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
        return true;
    }
    static constexpr unsigned int get_val(){
        for(unsigned int x=2; x<MOD; x++) if(examine_val(x)) return x;
        return 0;
    }
    static const unsigned int val = get_val();
};

}

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned int;
#define rep(i,n) for(int i=0; i<(n); i++)


using m32 = nachia::StaticModint<90007>;

i64 rev_int(i64 x){
    string a = to_string(x);
    reverse(a.begin(), a.end());
    i64 ans = 0;
    for(auto c : a) ans = ans * 10 + (c - '0');
    return ans;
}


int main() {
    i64 P,Q,x,y; cin >> P >> Q >> x >> y;

    i64 rev_off = y;
    while(rev_off % 10 == 0 || rev_int(rev_off) % 90007 == 0) rev_off += y;
    i64 rev_aoff = Q;
    while(rev_int(rev_aoff) % 90007 == (90007 - rev_int(rev_off) % 90007) % 90007) rev_aoff += Q;

    string rev_stry = to_string(rev_off); reverse(rev_stry.begin(), rev_stry.end());
    string rev_strQ = to_string(rev_aoff); reverse(rev_strQ.begin(), rev_strQ.end());
    i64 rev_y = 0; for(auto a : rev_stry) rev_y = rev_y * 10 + a - '0';
    i64 rev_Q = 0; for(auto a : rev_strQ) rev_Q = rev_Q * 10 + a - '0';

    m32 r_ans = m32(10).pow(rev_strQ.size()) * rev_y;
    m32 off_ans = m32(rev_Q);
    int len_r_ans = 0;
    while((r_ans + off_ans).val() != x){ len_r_ans++; r_ans *= 10; }
    cout << rev_stry << string(len_r_ans, '0') << rev_strQ << "\n";
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;