結果

問題 No.3081 Make Palindromic Multiple
ユーザー Rubikun
提出日時 2025-03-28 23:05:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 416 ms / 1,000 ms
コード長 4,156 bytes
コンパイル時間 2,360 ms
コンパイル使用メモリ 208,148 KB
実行使用メモリ 35,060 KB
最終ジャッジ日時 2025-03-28 23:06:06
合計ジャッジ時間 19,284 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=2000005,INF=15<<26;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


//int128

//https://kopricky.github.io/code/Misc/int128.html

// __int128の入出力

using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
    string s;
    is >> s;
    v = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
    }
    if (s[0] == '-') { v *= -1; }
    return is;
}

ostream& operator<<(ostream& os, const LL& v)
{
    if (v == 0) { return (os << "0"); }
    LL num = v;
    if (v < 0) {
        os << '-';
        num = -num;
    }
    string s;
    for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}

ll rui[MAX];

const int M=1000000;

pll MA[1000000];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    ll N;cin>>N;
    string S=to_string(N);
    string T=S;reverse(all(T));
    
    rui[0]=1;
    for(int i=1;i<MAX;i++){
        rui[i]=rui[i-1]*10%N;
    }
    
    ll K=rng()%(MAX/2);
    if(K<0) K+=(MAX/2);
    K+=(MAX/4);
    if(K&1) K++;
    
    LL now=(LL)stoll(T);
    now*=rui[K+si(S)];
    now+=stoll(S);
    now%=N;
    
    for(int i=0;i<1000000;i++){
        MA[i]=mp(-1,-1);
    }
    {
        string A(18,'0');
        ll sum=now;
        
        for(ll t=0;t<2000000;t++){
            int i=rng()%18;
            if(i<0) i+=18;
            
            int to=rng()%10;
            if(to<0) to+=10;
            
            sum-=rui[K/2+si(S)+17-i]*(A[i]-'0');
            sum-=rui[K/2+si(S)-1-(17-i)]*(A[i]-'0');
            
            A[i]=char('0'+to);
            
            sum+=rui[K/2+si(S)+17-i]*(A[i]-'0');
            sum+=rui[K/2+si(S)-1-(17-i)]*(A[i]-'0');
            sum%=N;
            
            ll z=N-sum;
            if(z>=N) z-=N;
            MA[z/M]=mp(z,stoll(A));
        }
    }
    
    ll ge=rng()%(K/8);
    if(ge<0) ge+=(K/8);
    ge+=33;
    
    string A(18,'0');
    ll sum=0;
    
    while(1){
        int i=rng()%18;
        if(i<0) i+=18;
        
        int to=rng()%10;
        if(to<0) to+=10;
        
        sum-=rui[K/2+si(S)+17-i+ge]*(A[i]-'0');
        sum-=rui[K/2+si(S)-1-ge-(17-i)]*(A[i]-'0');
        
        A[i]=char('0'+to);
        
        sum+=rui[K/2+si(S)+17-i+ge]*(A[i]-'0');
        sum+=rui[K/2+si(S)-1-ge-(17-i)]*(A[i]-'0');
        
        sum%=N;
        if(sum<0) sum+=N;
        
        if(MA[sum/M].fi==sum){
            ll t=MA[sum/M].se;
            string B=to_string(t);
            while(si(B)<18) B="0"+B;
            //cout<<K<<endl;
            cout<<10<<"\n";
            cout<<T<<" "<<1<<"\n";
            cout<<0<<" "<<(K/2-(ge+18))<<"\n";
            cout<<A<<" "<<1<<"\n";
            cout<<0<<" "<<ge-18<<"\n";
            cout<<B<<" "<<1<<"\n";
            
            reverse(all(A));
            reverse(all(B));
            
            cout<<B<<" "<<1<<"\n";
            cout<<0<<" "<<ge-18<<"\n";
            cout<<A<<" "<<1<<"\n";
            cout<<0<<" "<<(K/2-(ge+18))<<"\n";
            cout<<S<<" "<<1<<"\n";
            
            return 0;
        }
    }
}
0