結果

問題 No.1006 Share an Integer
ユーザー yohaku0v0
提出日時 2024-04-21 22:10:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,610 bytes
コンパイル時間 4,908 ms
コンパイル使用メモリ 291,596 KB
実行使用メモリ 14,828 KB
最終ジャッジ日時 2024-10-13 20:34:47
合計ジャッジ時間 7,616 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pli=pair<ll,int>;
using pil=pair<int,ll>;
using pdd=pair<ld,ld>;
using vi=vector<int>;
using vpi=vector<pii>;
using vl=vector<ll>;
using vs=vector<string>;
using vc=vector<char>;
using vd=vector<ld>;
using vpl=vector<pll>;
using vpil=vector<pair<int,ll>>;
using vpli=vector<pair<ll,int>>;
using vpd=vector<pdd>;
using vb=vector<bool>;
template<class T> using pq=priority_queue<T,vector<T>,greater<T>>;
template<class T> using rpq=priority_queue<T,vector<T>>;
template<class T> using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define ovl4(a,b,c,d,name,...) name
#define rep(...) ovl4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rep1(a) for(int i=0; i<a; i++)
#define rep2(i,a) for(int i=0; i<a; i++)
#define rep3(i,a,b) for(int i=a; i<b; i++)
#define rep4(i,a,b,c) for(int i=a; i<b; i+=c)
#define rrep(...) ovl4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define rrep1(a) for(int i=a; i>=0; i--)
#define rrep2(i,a) for(int i=a; i>=0; i--)
#define rrep3(i,a,b) for(int i=a; i>=b; i--)
#define rrep4(i,a,b,c) for(int i=a; i>=b; i-=c)
#define atrep(i,v) for(auto i:v)
void in(){}
template<class... T>void in(T&... a){(cin >>... >>a);}
template<class T>
void vin(vector<T> &v,int n=-1,int s=0){if(n==-1)n=v.size();rep(i,s,s+n)in(v[i]);}
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
void VIN(){}
template<class T,class... Ts>
void VIN(int ind,vector<T>& v,Ts&... vs){vin<T>(v,v.size()-ind,ind);if constexpr(sizeof...(vs)>0)VIN(ind,vs...);}
template<class T,class U>
void setin(vector<T> &a,vector<U> &b,int ind=0,int n=-1){if(n==-1)n=a.size();rep(i,ind,n)in(a[i],b[i]);}
template<class T,class... Ts>
bool chmax(T &a,Ts... b){T c=a;for(auto i:{b...})a=max(a,i);return a==c;}
template<class T,class...Ts>
bool chmin(T &a,Ts... b){T c=a;for(auto i:{b...})a=min(a,i);return a==c;}
void print(){cout<<"\n";}
template<class T,class... Ts>
void print(const T &a,const Ts&... b){cout <<a;(cout<<... <<(cout<<" ",b));cout<<"\n";}
template<class T>
void vprint(vector<T> &v,bool ind1=false,string aid=" "){rep(i,(int)ind1,v.size()){if(i>(int)ind1){cout <<aid;}cout <<v[i];}print();}
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Sort(a) sort(all(a))
#define rsort(a) sort(rall(a))
#define Uniq(a) a.erase(unique(all(a)),a.end())
#define elif else if
#define cY cout <<"Yes\n"
#define cN cout <<"No\n"
void yn(bool b){if(b){cY;}else{cN;}}
#define ft first
#define sd second
#define inr(l,x,r) (l<=x && x<=r)
#define hinr(l,x,r) (l<=x && x<r)
#define ingrid(i,a,b,h,w) (inr(i,a,h+i-1) && inr(i,b,w+i-1))
#define FIX fixed <<setprecision(15)
template<class T>
bool eql(const T &a){return true;};
template<class T,class... Ts>
bool eql(const T& a,const Ts&... b){bool ret=true;for(auto i:{b...})ret&=(i==a);return ret;}
bool operator==(const string& a,const string& b){return a.compare(b)==0;}
random_device rd;
mt19937 mt(rd());
const int INF=1e9;
const ll LINF=1e18;
const ll MOD=1e9+7;
const ll MMOD=998244353;
const ld eps=1e-10;
bool deql(const ld &a){return true;}
template<typename... Args>
bool deql(const ld& a,const Args&... b){bool ret=true;for(auto i:{b...})ret&=(inr(-eps,i-a,eps));return ret;}
int dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};

class prime{
    private:
    vl a1={2,7,61};
    vl a2={2,325,9375,28178,450775,9780504,1795265022};
    __int128_t modpow(__int128_t a,__int128_t b,__int128_t mod=MOD){
        __int128_t ret=1;
        a%=mod;
        while(b>0){if(b&1)ret=(ret*a)%mod;a=(a*a)%mod;b>>=1;}
        return ret;
    }
    bool is_prime(ll n,vl& A){
        ll s=0,d=n-1;
        while(!(d&1)){++s;d>>=1;}
        for(auto a:A){
            if(n<=a)return true;
            ll t,y=modpow(a,d,n);
            if(y!=1){
                for(t=0;t<s;t++){
                    if(y==n-1)break;
                    y=__int128_t(y)*y%n;
                }
                if(t==s)return false;
            }
        }
        return true;
    }
    ll findfactor(ll n){
        if(!(n&1))return 2;
        ll s=0;
        while(true){
            s++;
            ll x=2,y=2,d=1;
            auto f=[&](ll x)->ll{return ((__int128_t)x*x+s)%n;};
            while(d==1){
                x=f(x),y=f(f(y));
                d=gcd(abs(x-y),n);
            }
            if(d!=1 && d!=n)return d;
        }
    }
    void factor_dfs(int idx,ll val,vl &ret,vpli &fac){
        int size=fac.size();
        if(idx==size){ret.push_back(val);return;}
        ll v=fac[idx].ft;
        int c=fac[idx].sd;
        ll m=1;
        for(int i=0; i<=c; i++){
            factor_dfs(idx+1,val*m,ret,fac);
            m*=v;
        }
        return;
    }
    public:
    bool isprime(ll n){
        if(n<=1)return false;
        if(n==2)return true;
        if(n&1==0)return false;
        if(n<4759123141LL)return is_prime(n,a1);
        else return is_prime(n,a2);
    }
    map<ll,int> factorize(ll n){
        map<ll,int> ret;
        if(n==1)return ret;
        if(isprime(n)){
            ret[n]=1;
            return ret;
        }
        ll fac=findfactor(n);
        ret=factorize(fac);
        map<ll,int> ret_=factorize(n/fac);
        if(ret.size()>ret_.size()){for(auto i:ret_){ret[i.ft]+=i.sd;}return ret;}
        else{for(auto i:ret){ret_[i.ft]+=i.sd;}return ret_;}
    }
    vl enumerate(ll n){
        map<ll,int> f=factorize(n);
        vpli fac;
        for(auto i:f)fac.push_back(i);
        vl ret;
        factor_dfs(0,1,ret,fac);
        return ret;
    }
};
int main(){
    ios::sync_with_stdio(false);std::cin.tie(nullptr);
    INT(x);
    prime p;
    auto d=[](prime p,int n){return p.enumerate(n).size();};
    auto f=[d](prime p,int n)->int{return n-d(p,n);};
    vector<pair<int,pii>> ans;
    rep(a,1,x){
        int b=x-a;
        int k=abs(f(p,a)-f(p,b));
        pair<int,pii> pa={k,{a,b}};
        ans.push_back(pa);
    }
    Sort(ans);
    int val=ans[0].ft;
    atrep(i,ans){
        if(i.ft!=val)break;
        print(i.sd.ft,i.sd.sd);
    }
    return 0;
}
0