Submission #67550430

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=l;i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;

//math
namespace nouka28{
	random_device rnd; 
	mt19937 mt(rnd());
	const long long MT_MAX=(1LL<<62)-1;
	uniform_int_distribution<long long> rd(0,MT_MAX);
	double randd(){
		return 1.0*rd(mt)/MT_MAX;
	}
	long long randint(long long a,long long b){
		// [a,b]の乱数を生成
		return a+rd(mt)%(b-a+1);
	}

    template<class T=long long>
    vector<T> Quotients(T n){
        vector<T> retl,retr;
        for(int i=1;i*i<=n;i++){
            retl.push_back(i);
            if(i<n/i)retr.push_back(n/i);
        }
        reverse(retr.begin(),retr.end());
        retl.insert(retl.end(),retr.begin(),retr.end());
        return retl;
    }
    template<class T=long long>T ceil_sqrt(T n){
        T l=-1,r=n;
        while(r-l>1){
            T m=(l+r)>>1;
            if(m*m>=n)r=m;
            else l=m;
        }
        return r;
    }

    //ceil(a/b)
    template<class T=long long>T ceil(T a,T b){
        if(a>=0){
            return (a+b-1)/b;
        }else{
            return (a)/b;
        }
    };

    //floor(a/b)
    template<class T=long long>T floor(T a,T b){
        if(a>=0){
        return a/b;
        }else{
            return -(-a+b-1)/b;
        }
    };

    //x^y mod m
    template<class T=long long>T modpow(T x,T y,T m){
        T res=1%m;x%=m;
        while(y){
            if(y%2)res=(res*x)%m;
            x=(x*x)%m;
            y>>=1;
        }
        return res;
    }

    //a^0+a^1+..+a^(n-1) (mod m)
    template<class T>
    T geometric_progression(T a,T n,T m){
        if(n==0)return 0;
        if(n%2==1){
            return (geometric_progression(a,n-1,m)*a+1)%m;
        }else{
            return (geometric_progression(a*a%m,n/2,m)*(1+a))%m;
        }
    };

    //素数判定(高速)
    bool is_prime(long long n){
        if(n<=1)return 0;
        if(n==2)return 1;
        if(n%2==0)return 0;
        long long s=0,d=n-1;
        while(d%2==0)d/=2,s++;
        if(n<4759123141LL){
            for(long long e:{2,7,61}){
                if(n<=e)break;
                long long t,x=modpow<__int128_t>(e,d,n);
                if(x!=1){
                    for(t=0;t<s;t++){
                        if(x==n-1)break;
                        x=__int128_t(x)*x%n;
                    }
                    if(t==s)return 0;
                }
            }
            return 1;
        }else{
            for(long long e:{2,325,9375,28178,450775,9780504,1795265022}){
                if(n<=e)break;
                long long t,x=modpow<__int128_t>(e,d,n);
                if(x!=1){
                    for(t=0;t<s;t++){
                        if(x==n-1)break;
                        x=__int128_t(x)*x%n;
                    }
                    if(t==s)return 0;
                }
            }
            return 1;   
        }
    }

    //Xor Shift
    unsigned xor_shift_rng(){
        static unsigned tx=123456789,ty=362436069,tz=521288629,tw=88675123;
        unsigned tt=(tx^(tx<<11));
        tx=ty,ty=tz,tz=tw;
        return (tw=(tw^(tw>>19))^(tt^(tt>>8)));
    }

    //ロー法 Nを割り切る素数を見つける
    long long pollard(long long n){
        if(n%2==0)return 2;
        if(is_prime(n))return n;
        long long step=0;
        while(true){
            long long r=(long long)xor_shift_rng();
            auto f=[&](long long x)->long long {return ((__int128_t(x)*x)%n+r)%n;};
            long long x=++step,y=f(x);
            while(true){
                long long p=gcd(abs(y-x),n);
                if(p==0||p==n)break;
                if(p!=1)return p;
                x=f(x);
                y=f(f(y));
            }
        }
    }

    //internal fast factrize vector
    void _internal_factrize_vector(long long n,vector<long long>&v){
        if(n==1)return;
        long long p=pollard(n);
        if(p==n){v.push_back(p);return;}
        _internal_factrize_vector(p,v);
        _internal_factrize_vector(n/p,v);
    }

    //fast factrize vector
    vector<long long> factrize_vector(long long n){
        vector<long long> res;
        _internal_factrize_vector(n,res);
        sort(res.begin(),res.end());
        return res;
    }

    //internal fast factrize map
    void _internal_factrize_map(long long n,map<long long,long long>&v){
        if(n==1)return;
        long long p=pollard(n);
        if(p==n){v[p]++;return;}
        _internal_factrize_map(p,v);
        _internal_factrize_map(n/p,v);
    }

    //fast factrize map
    map<long long,long long> factrize_map(long long n){
        map<long long,long long> res;
        _internal_factrize_map(n,res);
        return res;
    }

    //fast factor
    vector<long long> factor(long long n){
        map<long long,long long> fm;_internal_factrize_map(n,fm);
        vector<long long> res={1};
        for(auto[i,j]:fm){
            vector<long long> tmp;
            int p=1;
            for(long long k=0;k<=j;k++){
                for(auto e:res){
                    tmp.push_back(e*p);
                }
                p*=i;
            }
            swap(res,tmp);
        }
        return res;
    }

    //euler phi function
    long long euler_phi(long long n){
        vector<long long> ps=factrize_vector(n);
        ps.erase(unique(ps.begin(),ps.end()),ps.end());
        for(long long p:ps){
            n/=p;n*=(p-1);
        }
        return n;
    }

    //ax+by=gcd(a,b)
    template<class T=long long>
    tuple<T,T,T> extgcd(T a,T b){
        T x1=1,y1=0,d1=a,x2=0,y2=1,d2=b;
        while(d2!=0){
            T q=d1/d2,u=d1-d2*q,v=x1-x2*q,w=y1-y2*q;
            d1=d2;d2=u;x1=x2;x2=v;y1=y2;y2=w;
        }
        if(d1<0){
            d1=-d1;x1=-x1;y1=-y1;
        }
        return {d1,x1,y1};
    }

    //x inverse (mod m)
    long long modinv(long long a,long long m){
        long long b=m,u=1,v=0;
        while(b){
            long long t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        u%=m;
        if(u<0)u+=m;
        return u;
    }

	//find primitive root
	long long primitive_root(long long p){
		vector<long long> f=factrize_vector(p-1);
		f.erase(unique(f.begin(),f.end()),f.end());
		while(1){
			long long x=randint(1,p-1);
			bool flg=1;
			for(auto e:f)if(modpow<__int128_t>(x,(p-1)/e,p)==1){flg=0;break;}
			if(flg)return x;
		}
	}

    //x^k=y (mod m) gcd(x,m)=1 k>=0
    long long discrete_logarithm_coprime_mod(long long x,long long y,long long m){
        x%=m;y%=m;
        if(y==1||m==1){
            return 0;
        }
        if(x==0){
            if(y==0)return 1;
            else return -1;
        }
        long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
        unordered_map<long long,long long> mp;
        long long pow_x=1;
        for(long long i=0;i<M;i++){
            if(!mp.count(pow_x))mp[pow_x]=i;
            pow_x=pow_x*x%m;
        }
        long long ya=y;
        for(long long i=0;i<M;i++){
            if(mp.count(ya))return M*i+mp[ya];
            ya=ya*a%m;
        }
        return -1;
    }

    //x^k=y (mod m) gcd(x,m)=1 k>=1
    long long discrete_Nlogarithm_coprime_mod(long long x,long long y,long long m){
        if(m==1){
            if(x==1)return 1;
            else return -1;
        }
        if(x==0){
            if(y==0)return 1;
            else return -1;
        }
        long long M=ceil_sqrt(m),a=modpow(modinv(x,m),M,m);
        unordered_map<long long,long long> mp;
        long long pow_x=1;
        for(long long i=0;i<=M;i++){
            if(!mp.count(pow_x))mp[pow_x]=i;
            pow_x=pow_x*x%m;
        }
        long long ya=y;
        for(long long i=0;i<M;i++){
            if(ya==1&&i>0)return i*M;
            else if(mp.count(ya))return M*i+mp[ya];
            ya=ya*a%m;
        }
        return -1;
    }

    //x^k=y (mod m) k>=0
    long long discrete_logarithm_arbitrary_mod(long long x,long long y,long long m){
        if(m==1){
            return 0;
        }
        x%=m;y%=m;
        long long d,pow_x=1;
        for(d=0;;d++){
            if(!(m>>d))break;
            if(pow_x==y){
                return d;
            }
            pow_x=pow_x*x%m;
        }
        long long g=gcd(pow_x,m);
        if(y%g!=0){
            return -1;
        }
        m/=g;
        long long z=y*modinv(pow_x,m),t=discrete_logarithm_coprime_mod(x,z,m);
        if(t==-1)return -1;
        else return d+t;
    }

    //x^k=y (mod m) k>=1
    long long discrete_Nlogarithm_arbitrary_mod(long long x,long long y,long long m){
        if(m==1){
            if(x==1)return 1;
            else return -1;
        }
        x%=m;y%=m;
        long long d,pow_x=1;
        for(d=0;;d++){
            if(!(m>>d))break;
            if(pow_x==y&&d){
                return d;
            }
            pow_x=pow_x*x%m;
        }
        long long g=gcd(pow_x,m);
        if(y%g!=0){
            return -1;
        }
        m/=g;
        long long z=y*modinv(pow_x,m),t;
        if(d)t=discrete_logarithm_coprime_mod(x,z,m);
        else t=discrete_Nlogarithm_coprime_mod(x,y,m);
        if(t==-1)return -1;
        else return d+t;
    }
}

signed main(){
	int N;cin>>N;

	auto d=nouka28::Quotients(N);

	mint ans=0;
	for(auto&&e:d){
		// cout<<e<<endl;
		ans-=e*(N/e-N/(e+1));
	}

	ans+=mint(N)*(N+1)/2;

	cout<<ans.val()<<"\n";
}

Submission Info

Submission Time
Task E - Count A%B=C
User nouka28
Language C++ 20 (gcc 12.2)
Score 475
Code Size 10153 Byte
Status AC
Exec Time 36 ms
Memory 34676 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 475 / 475
Status
AC × 3
AC × 56
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 3552 KiB
00-sample-02.txt AC 1 ms 3548 KiB
00-sample-03.txt AC 24 ms 23280 KiB
01-01.txt AC 1 ms 3656 KiB
01-02.txt AC 2 ms 3416 KiB
01-03.txt AC 1 ms 3612 KiB
01-04.txt AC 1 ms 3508 KiB
01-05.txt AC 1 ms 3552 KiB
01-06.txt AC 1 ms 3548 KiB
01-07.txt AC 1 ms 3480 KiB
01-08.txt AC 1 ms 3552 KiB
01-09.txt AC 1 ms 3608 KiB
01-10.txt AC 1 ms 3612 KiB
01-11.txt AC 1 ms 3544 KiB
01-12.txt AC 1 ms 3548 KiB
01-13.txt AC 1 ms 3664 KiB
01-14.txt AC 1 ms 3480 KiB
01-15.txt AC 36 ms 34572 KiB
01-16.txt AC 35 ms 34672 KiB
01-17.txt AC 34 ms 34672 KiB
01-18.txt AC 34 ms 34676 KiB
01-19.txt AC 34 ms 34656 KiB
01-20.txt AC 33 ms 33688 KiB
01-21.txt AC 34 ms 34140 KiB
01-22.txt AC 33 ms 33352 KiB
01-23.txt AC 33 ms 33380 KiB
01-24.txt AC 34 ms 34144 KiB
01-25.txt AC 34 ms 34576 KiB
01-26.txt AC 33 ms 33864 KiB
01-27.txt AC 33 ms 33804 KiB
01-28.txt AC 1 ms 3484 KiB
01-29.txt AC 1 ms 3420 KiB
01-30.txt AC 1 ms 3608 KiB
01-31.txt AC 1 ms 3576 KiB
01-32.txt AC 1 ms 3452 KiB
01-33.txt AC 1 ms 3660 KiB
01-34.txt AC 1 ms 3764 KiB
01-35.txt AC 1 ms 3636 KiB
01-36.txt AC 2 ms 4124 KiB
01-37.txt AC 2 ms 4116 KiB
01-38.txt AC 2 ms 4772 KiB
01-39.txt AC 2 ms 4668 KiB
01-40.txt AC 3 ms 5248 KiB
01-41.txt AC 4 ms 5704 KiB
01-42.txt AC 26 ms 24632 KiB
01-43.txt AC 28 ms 27304 KiB
01-44.txt AC 8 ms 9420 KiB
01-45.txt AC 33 ms 32484 KiB
01-46.txt AC 13 ms 13944 KiB
01-47.txt AC 1 ms 3620 KiB
01-48.txt AC 15 ms 16876 KiB
01-49.txt AC 6 ms 8196 KiB
01-50.txt AC 23 ms 22224 KiB
01-51.txt AC 26 ms 24812 KiB
01-52.txt AC 5 ms 6920 KiB
01-53.txt AC 30 ms 29384 KiB