2019 ICPC Asia Yinchuan Regional

2019 ICPC Asia Yinchuan Regional

• F题.Function!

F题.Function!

题面

题目描述
输入
　　An integer n (2≤n≤10¹²) described above.
输出
　　An integer denotes the value you have calculated modulo 998244353998244353.
样例输入1

2

样例输出1

2

样例输入2

10

样例输出2

236

思路

题解
　n的范围为10¹²不能暴力，通过一系列公式推导进行化简，先是将范围缩减到10⁶仍然在最后一个测试点T掉，应该是用python语言（为了高精度)；进一步将范围缩减为10⁴通过。推导过程如下图：

源码

#python
from math import log
mod=998244353
#快速幂
def fun(a,n):
    ans=1
    while(n!=0):
        if(n&1==1):
            ans*=a
        a=a*a
        n>>=1
    return ans
n=int(input())
t=(int)((n+1)**0.5)+1
t1=(int)(n**(1/3))+1
t2=(int)((n+1)**0.5)
ans=0
if n-t+1>=1:#1的个数
    ans=ans+((n+1)*(t+n)*(n+1-t)//2-n*(2*n+1)*(n+1)//6+(t-1)*(2*t-1)*t//6)%mod
    ans%=mod
#print(ans)
if t2-t1+1>=1:#2的个数
    ans=ans+((t1+t2)*(t2-t1+1)*(n+1)-t2**2*(t2+1)**2//4+(t1-1)**2*t1**2//4-t2*(2*t2+1)*(t2+1)//6+(t1-1)*(2*t1-1)*t1//6)%mod
    ans%=mod
#print(ans)
for a in range(2,t1):
    x=(int)(log(n+1)/log(a))
    ax=fun(a,x+2)
    ans=ans+(a*x*(n+1)-(ax-a**2)//(a-1))%mod
    ans%=mod
    #print(a,x,ax,ans)
print(ans)