T1
正解：莫反推导出来的整除分块，证明不会：
然后直接快速幂来算是 \(O(\sqrt{m}·log\:n)\) 的，过不了剩下三个点。考虑到模数很小且为质数，用费马小定理预处理幂次然后去算，复杂度 \(O(\mathbf{10007}·log\:n+\sqrt{m})\)，注意字符串处理 \(n\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1145140,M=1919810,mod=10007;
ll n,m,num[N];
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll ans=0,l=1,r;
int main(){
//ios::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
char c;
while((c=getchar())!=' ') n=(n*10+c-'0')%(mod-1);
cin>>m;
for(int i=0;i<mod;++i) num[i]=qpow(i,n);
for( ;l<=m; ){
//cout<<"QWQ";
r=m/(m/l);
ans+=num[m/l%mod]*(r-l+1)%mod;
ans%=mod;
l=r+1;
}
cout<<ans%mod;
return 0;
}
T2
贪心假了，还忘记输出小数点了，宝玲。看不懂题解。
T3
正解树套树，wyc用分块切了，强。