1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<set> #include<bitset> #include<assert.h> #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,l,r) for(int i=l;i>=r;i--) #define link(x) for(edge *j=h[x];j;j=j->next) #define mem(a) memset(a,0,sizeof(a)) #define ll long long #define eps 1e-12 #define succ(x) (1LL<<(x)) #define lowbit(x) (x&(-x)) #define sqr(x) ((x)*(x)) #define mid ((x+y)>>1) #define NM 10000005 #define nm 11 #define pi 3.1415926535897931 const ll inf=998244353; using namespace std; ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f*x; }
template <class T> void read(T &x) { static char ch;static bool neg; for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar()); for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar()); x=neg?-x:x; }
__int128 p; int n,prime[NM],tot,phi[NM]; ll ans,_x,_y,pre[NM],sum[NM]; bool v[NM];
void init(){ n=1e7;phi[1]=1; inc(i,1,n)sum[i]=(sum[i-1]+i)%inf,pre[i]=(pre[i-1]+1ll*i*i)%inf; inc(i,2,n){ if(!v[i])prime[++tot]=i,phi[i]=i-1; inc(j,1,tot){ if(i*prime[j]>n)break; v[i*prime[j]]++; if(i%prime[j]==0){ phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } }
int main(){ init(); int _=read();while(_--){ read(p); for(__int128 x=0,y=1e7;x<=y;){ __int128 t=x+y>>1; if(t*t*t<=p)n=t,x=t+1;else y=t-1; } n--;ans=1ll*n*(n+1)/2%inf; for(int i=1;i<=n;i++){ ans+=3ll*phi[i]*i%inf*pre[n/i]%inf; ans+=3ll*phi[i]*sum[n/i]%inf; ans%=inf; } n++; __int128 t=n;t=t*t*t-1; for(int i=1;i*i<=n;i++)if(n%i==0){ ans+=phi[i]*(p/i%inf-t/i%inf+inf)%inf; if(i*i<n)ans+=phi[n/i]*(p/(n/i)%inf-t/(n/i)%inf+inf)%inf; ans%=inf; } printf("%lld\n",ans); } return 0; }
|