【題解】HDU6760 Math is Simple (差分)

好nb的題啊

求\(n\le 1e8\)，

\(T\le 1e4\)組詢問(但是你他嗎std不是\(O(n)\)的復雜度嗎)

那么

設\(g(n)=\sum_{a<b,a+b=n,a\perp b} {1\over ab}\)

其實

所以

所以

然后他媽的"You can pre-calculate all \(h_{0\dots 10^8}\) values in a second, or so."

//@winlere
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#pragma GCC optimize(3)

using namespace std; typedef long long ll;
int qr(){
	int ret=0,c=getchar(),f=0;
	while(!isdigit(c)) f|=c==45,c=getchar();
	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
	return f?-ret:ret;
}
const int mod=998244353;
const int inv2=(mod+1)/2;
int h[int(1e8+5)],M[int(1e4+5)],REM[int(1e4+5)];
int MOD(const int&x){return x>=mod?x-mod:x;}
int MOD(const int&x,const int&y){return 1ll*x*y%mod;}

int mu(int n){
	int ret=0;
	for(int t=2;t*t<=n;++t)
		if(n%t==0){
			int cnt=0;
			while(n%t==0) n/=t,++cnt;
			if(cnt>1) return 0;
			++ret;
		}
	if(n>1) ++ret;
	return ret&1?-1:1;
}

int main(){
	h[1]=1;
	for(int t=2;t<=1e8;++t){
		int g=mod/t;
		h[t]=MOD(mod-g,h[mod-g*t]);
	}
	for(int t=2;t<=1e8;++t) h[t]=MOD(h[t-1]+h[t]);
	int T=qr();
	while(T--){
		int n=qr();
		ll ans=0;
		if(n==2){printf("%d\n",inv2); continue;}
		for(int t=1;t*t<=n;++t)
			if(n%t==0){
				int g=n/t;
				ans+=MOD(h[g],mu(t)*(h[t]-h[t-1]));
				if(t*t!=n) ans+=MOD(h[t],mu(g)*(h[g]-h[g-1]));
			}
		printf("%d\n",MOD(MOD(h[n]-h[n-1]+mod,ans%mod+mod)+inv2));
	}
	return 0;
}