织梦系统做的网站忘记登录密码,网站视频如何下载,网站备案帐号找回,微信小程序注册需要多少钱正题 题目大意
定义函数f(x)f(x)f(x)表示有多少长度为nnn的序列使得其中全都是xxx的约束#xff0c;然后每个序列的贡献是这个序列的gcdgcdgcd再gcdgcdgcd上一个BBB。
给出n,m,Bn,m,Bn,m,B#xff0c;求∑i1mf(i)\sum_{i1}^mf(i)∑i1mf(i)。 解题思路
我们发现fff是一个…正题 题目大意
定义函数f(x)f(x)f(x)表示有多少长度为nnn的序列使得其中全都是xxx的约束然后每个序列的贡献是这个序列的gcdgcdgcd再gcdgcdgcd上一个BBB。
给出n,m,Bn,m,Bn,m,B求∑i1mf(i)\sum_{i1}^mf(i)∑i1mf(i)。 解题思路
我们发现fff是一个积性函数所以我们考虑用线性筛。
首先我们要预处理出所以f(pc)f(p^c)f(pc)(ppp为质数)我们定义ddd为最大的一个xxx使得px∣Bp^x|Bpx∣B有 f(pc){∑i0cpi∗[(c−i1)n−(c−i)n](c≤d)pd∗(c−d1)n∑i0d−1pi∗[(c−i1)n−(c−i)n](cd)f(p^c)\left\{\begin{matrix} \sum_{i0}^c p^i*[(c-i1)^n-(c-i)^n]\ \ \ \ \ (c\leq d) \\\ p^d*(c-d1)^n\sum_{i0}^{d-1} p^i*[(c-i1)^n-(c-i)^n] \ \ \ \ (cd) \end{matrix}\right.f(pc){∑i0cpi∗[(c−i1)n−(c−i)n] (c≤d) pd∗(c−d1)n∑i0d−1pi∗[(c−i1)n−(c−i)n] (cd)
然后我们发现此式子可以递推然后用积性函数的性质然后可以做到O(m)O(m)O(m)推出f(1∼m)f(1\sim m)f(1∼m) codecodecode
/*#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)*/
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll XJQ998244353,N21000000;
ll n,m,f[N],ans,p[80],pri[N],cnt,B;
bool v[N];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ans(ll)ans*x%XJQ;x(ll)x*x%XJQ;b1;}return ans;
}
int main()
{//freopen(sequence.in,r,stdin);//freopen(sequence.out,w,stdout);scanf(%lld%lld%lld,n,m,B);f[1]1;p[1]1;for(ll i1;i60;i)p[i]power(i,n);for(ll i2;im;i){if(!v[i]){ll d0,P1,last1;pri[cnt]i; while(!(B%i)) B/i,d; for(ll ji,c1;jm;j*i,c){v[j]1;if(cd){(f[j]f[j/i]*i%XJQp[c1]-p[c]XJQ)%XJQ;lastf[j];Pj;}else{f[j](last*i%XJQp[c1]-p[c])%XJQ-(P*i)%XJQ*(p[c-d]-p[c-d-1])%XJQ;lastf[j];(f[j]P*p[c-d])%XJQ;f[j](f[j]XJQ)%XJQ; }}}for(ll j1;jcnt;j){if(!(i%pri[j])||i*pri[j]m) break;//v[pri[j]*i]1;for(ll kpri[j];i*km;k*pri[j])v[i*k]1,f[i*k]f[i]*f[k]%XJQ;}}for(ll i1;im;i)(ansf[i])%XJQ;printf(%lld,ans);
}
