結果

問題 No.1781 LCM
コンテスト
ユーザー chocorusk
提出日時 2021-12-10 22:44:15
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 2,850 ms / 5,000 ms
コード長 3,106 bytes
コンパイル時間 10,652 ms
コンパイル使用メモリ 163,212 KB
実行使用メモリ 22,180 KB
最終ジャッジ日時 2024-11-15 22:23:48
合計ジャッジ時間 27,656 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
using mint=modint998244353;
const int MAX=1000000;
bitset<MAX> isprime;
void sieve(){
	for(int i=3; i<MAX; i++, i++) isprime[i]=1;
	isprime[2]=1;
	for(int i=3; i<MAX; i++){
		if(isprime[i]){
			for(int j=(i<<1); j<MAX; j+=i) isprime[j]=0;
		}
	}
}
ll p[MAX], n, sq;
int isq;
vector<ll> divs, pc;
inline ll idx(ll x){
	return (x<=sq)?x-1:(ll)divs.size()-n/x;
}
void calc(){
	sieve();
	while((sq+1)*(sq+1)<=n) sq++;
	for(int i=1; i<=sq; i++) divs.push_back(i);
	for(int i=sq; i>=1; i--) if(n/i>sq) divs.push_back(n/i);
	int k=0; isq=-1;
	for(int i=2; i<MAX; i++){
		if(isprime[i]){
            p[k]=i;
            if(i>sq && isq==-1) isq=k;
            k++;
		}
	}
}
void primecount(){
	vector<ll> dp=divs;
	pc.resize(divs.size(), -1);
	int l;
	for(l=0; l<divs.size() && divs[l]<p[0]*p[0]; l++){
		if(divs[l]<=1) pc[l]=0;
		else if(divs[l]==2) pc[l]=1;
		else pc[l]=2;
	}
	for(int i=1; i<=isq; i++){
		int r=lower_bound(divs.begin(), divs.end(), p[i]*p[i])-divs.begin();
		for(int j=(int)divs.size()-1; j>=l; j--){
			int k=idx(divs[j]/p[i-1]);
			if(pc[k]!=-1) dp[j]-=pc[k]-i+2;
			else dp[j]-=dp[k];
		}
		for(int j=l; j<r; j++) pc[j]=dp[j]+i-1;
		l=r;
	}
}
mint ans;
ll len;
mint c[40];
vector<mint> solve(){
	vector<mint> dp(divs.size());
	for(int i=isq-1; i>=0; i--){
		int l=lower_bound(divs.begin(), divs.end(), p[i]*p[i])-divs.begin();
		for(int j=(int)divs.size()-1; j>=l; j--){
			mint a=dp[j];
			if(p[i+1]*p[i+1]>divs[j]){
                //assert(pc[j]>=i+1);
                a=1+mint(pc[j]-i-1)*c[1];
            }
            ll x=divs[j]/p[i];
            int e=1;
            while(x){
                int k=idx(x);
                mint b=dp[k];
                if(x<p[i+1]) b=1;
                else if(p[i+1]*p[i+1]>divs[k]){
                    //assert(pc[k]>=i+1);
                    b=1+mint(pc[k]-i-1)*c[1];
                }
                a+=b*c[e];
                x/=p[i];
                e++;
            }
            dp[j]=a;
		}
	}
    for(int i=0; i<divs.size() && divs[i]<4; i++){
        dp[i]=1;
        for(int j=2; j<=divs[i]; j++){
            dp[i]+=c[1];
        }
    }
    return dp;
}
int main()
{
	cin>>len>>n;
    for(int i=1; i<40; i++){
        c[i]=mint(i+1).pow(len)-mint(i).pow(len);
    }
	calc(); primecount();
    auto dp=solve();
    // for(auto x:divs){
    //     cout<<x<<" "<<pc[idx(x)]<<" "<<dp[idx(x)].val()<<endl;
    // }
    for(auto x:divs){
        ans+=mint(x)*(dp[idx(n/x)]-dp[idx(n/(x+1))]);
    }
    cout<<ans.val()<<endl;
	return 0;
}
0