当前位置:网站首页>[hdu6833] a very easy math problem
[hdu6833] a very easy math problem
2022-04-23 09:42:00 【Zimba_】
The question :
Given a positive integer T , k , x T,k,x T,k,x, Next T T T Group example , Each set of examples gives a positive integer n n n, For each n n n, Ask for
∑ a 1 = 1 n ∑ a 2 = 1 n … ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g c d ( a 1 , a 2 , … , a x ) ) g c d ( a 1 , a 2 , … , a x ) \sum_{a_{1}=1}^{n}\sum_{a_{2}=1}^{n}…\sum_{a_{x}=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(gcd(a_{1},a_{2},…,a_{x}))gcd(a_{1},a_{2},…,a_{x}) a1=1∑na2=1∑n…ax=1∑n(j=1∏xajk)f(gcd(a1,a2,…,ax))gcd(a1,a2,…,ax)
among f ( x ) f(x) f(x) Is defined as , When x x x When there is a square factor , f ( x ) = 0 f(x)=0 f(x)=0, otherwise f ( x ) = 1 f(x)=1 f(x)=1.
( 1 ≤ T ≤ 1 0 4 , 1 ≤ k , x ≤ 1 0 9 , 1 ≤ n ≤ 2 × 1 0 5 ) (1\leq T \leq 10^{4},1\leq k,x \leq 10^{9},1\leq n \leq 2\times 10^{5}) (1≤T≤104,1≤k,x≤109,1≤n≤2×105)
deduction :
Routine proposal g c d gcd gcd, become
∑ g = 1 n ∑ a 1 = 1 n ∑ a 2 = 1 n … ∑ a x = 1 n ( ∏ j = 1 x a j k ) f ( g ) g [ g = g c d ( a 1 , a 2 , … , a x ) ] \sum_{g=1}^{n}\sum_{a_{1}=1}^{n}\sum_{a_{2}=1}^{n}…\sum_{a_{x}=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})f(g)g[g=gcd(a_{1},a_{2},…,a_{x})] g=1∑na1=1∑na2=1∑n…ax=1∑n(j=1∏xajk)f(g)g[g=gcd(a1,a2,…,ax)]
Then adjust the formula. ,
∑ g = 1 n g [ g No save stay flat Fang because Son ] ∑ a 1 = 1 n ∑ a 2 = 1 n … ∑ a x = 1 n ( ∏ j = 1 x a j k ) [ g = g c d ( a 1 , a 2 , … , a x ) ] \sum_{g=1}^{n}g[g There is no square factor ]\sum_{a_{1}=1}^{n}\sum_{a_{2}=1}^{n}…\sum_{a_{x}=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})[g=gcd(a_{1},a_{2},…,a_{x})] g=1∑ng[g No save stay flat Fang because Son ]a1=1∑na2=1∑n…ax=1∑n(j=1∏xajk)[g=gcd(a1,a2,…,ax)]
We make f ( g ) f(g) f(g),
f ( g ) = ∑ a 1 = 1 n ∑ a 2 = 1 n … ∑ a x = 1 n ( ∏ j = 1 x a j k ) [ g = g c d ( a 1 , a 2 , … , a x ) ] f(g)=\sum_{a_{1}=1}^{n}\sum_{a_{2}=1}^{n}…\sum_{a_{x}=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})[g=gcd(a_{1},a_{2},…,a_{x})] f(g)=a1=1∑na2=1∑n…ax=1∑n(j=1∏xajk)[g=gcd(a1,a2,…,ax)]
then F ( g ) = ∑ g ∣ d f ( d ) F(g)=\sum_{g|d}f(d) F(g)=∑g∣df(d),
F ( g ) = ∑ g ∣ d f ( d ) = ∑ a 1 = 1 n ∑ a 2 = 1 n … ∑ a x = 1 n ( ∏ j = 1 x a j k ) [ g ∣ g c d ( a 1 , a 2 , … , a x ) ] = ∑ g ∣ a 1 ∑ g ∣ a 2 … ∑ g ∣ a x ( ∏ j = 1 x a j k ) = ∑ a 1 = 1 ⌊ n g ⌋ ∑ a 2 = 1 ⌊ n g ⌋ … ∑ a x = 1 ⌊ n g ⌋ ( ∏ j = 1 x a j k g k ) = ∑ a 1 = 1 ⌊ n g ⌋ a 1 k g k ∑ a 2 = 1 ⌊ n g ⌋ a 2 k g k … ∑ a x = 1 ⌊ n g ⌋ a x k g k = g x k ( ∑ a = 1 ⌊ n g ⌋ a k ) x F(g)=\sum_{g|d}f(d)=\sum_{a_{1}=1}^{n}\sum_{a_{2}=1}^{n}…\sum_{a_{x}=1}^{n}(\prod_{j=1}^{x}a_{j}^{k})[g|gcd(a_{1},a_{2},…,a_{x})]\\ =\sum_{g|a_{1}}\sum_{g|a_{2}}…\sum_{g|a_{x}}(\prod_{j=1}^{x}a_{j}^{k})\\ =\sum_{a_{1}=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{a_{2}=1}^{\lfloor \frac{n}{g} \rfloor}…\sum_{a_{x}=1}^{\lfloor \frac{n}{g} \rfloor}(\prod_{j=1}^{x}a_{j}^{k}g^{k})\\ =\sum_{a_{1}=1}^{\lfloor \frac{n}{g} \rfloor}a_{1}^{k}g^{k}\sum_{a_{2}=1}^{\lfloor \frac{n}{g} \rfloor}a_{2}^{k}g^{k}…\sum_{a_{x}=1}^{\lfloor \frac{n}{g} \rfloor}a_{x}^{k}g^{k}\\ =g^{xk}(\sum_{a=1}^{\lfloor \frac{n}{g} \rfloor}a^{k})^{x} F(g)=g∣d∑f(d)=a1=1∑na2=1∑n…ax=1∑n(j=1∏xajk)[g∣gcd(a1,a2,…,ax)]=g∣a1∑g∣a2∑…g∣ax∑(j=1∏xajk)=a1=1∑⌊gn⌋a2=1∑⌊gn⌋…ax=1∑⌊gn⌋(j=1∏xajkgk)=a1=1∑⌊gn⌋a1kgka2=1∑⌊gn⌋a2kgk…ax=1∑⌊gn⌋axkgk=gxk(a=1∑⌊gn⌋ak)x
hold F ( g ) F(g) F(g) After simplification , It's a little bit easier , Keep it for standby .
Then inversion is carried out against the original formula subset ,
∑ g = 1 n g [ g no Yes flat Fang because Son ] f ( g ) = ∑ g = 1 n [ g no Yes flat Fang because Son ] ∑ g ∣ d μ ( d g ) F ( d ) = ∑ g = 1 n g [ g no Yes flat Fang because Son ] ∑ g ∣ d μ ( d g ) d x k ( ∑ a = 1 ⌊ n d ⌋ a k ) x \sum_{g=1}^{n}g[g There is no square factor ]f(g)=\sum_{g=1}^{n}[g There is no square factor ]\sum_{g|d}\mu(\frac{d}{g}) F(d) \\ =\sum_{g=1}^{n}g[g There is no square factor ]\sum_{g|d}\mu(\frac{d}{g})d^{xk}(\sum_{a=1}^{\lfloor \frac{n}{d} \rfloor}a^{k})^{x} g=1∑ng[g no Yes flat Fang because Son ]f(g)=g=1∑n[g no Yes flat Fang because Son ]g∣d∑μ(gd)F(d)=g=1∑ng[g no Yes flat Fang because Son ]g∣d∑μ(gd)dxk(a=1∑⌊dn⌋ak)x
It is now ready for preprocessing ( ∑ a = 1 ⌊ n d ⌋ a k ) x (\sum_{a=1}^{\lfloor \frac{n}{d} \rfloor}a^{k})^{x} (∑a=1⌊dn⌋ak)x then o ( n l o g n ) o(nlogn) o(nlogn) Did , But it's not complicated enough , We consider number theory blocking .
We use some functions to replace some things in it , Make it look more elegant .
We use it i s ( t ) is(t) is(t) Express t t t Is there a square factor , Sometimes for 0 0 0, Otherwise 1 1 1.
Reuse A ( t ) = ( ∑ a = 1 t a k ) x A(t)=(\sum_{a=1}^{t}a^{k})^{x} A(t)=(∑a=1tak)x
The original form becomes ,
∑ g = 1 n i s ( g ) g ∑ g ∣ d μ ( d g ) d x k A ( ⌊ n d ⌋ ) \sum_{g=1}^{n}is(g)g\sum_{g|d}\mu(\frac{d}{g})d^{xk}A(\lfloor \frac{n}{d} \rfloor) g=1∑nis(g)gg∣d∑μ(gd)dxkA(⌊dn⌋)
The current formula still can't be divided into numbers . Be careful , We are now enumerating g g g, Reuse d d d enumeration g g g Multiple . We convert it into enumeration d d d, Enumerate again d d d Factor of g g g In the form of , It becomes ,
∑ d = 1 n d x k A ( ⌊ n d ⌋ ) ∑ g ∣ d μ ( d g ) i s ( g ) g \sum_{d=1}^{n}d^{xk}A(\lfloor \frac{n}{d} \rfloor)\sum_{g|d}\mu(\frac{d}{g})is(g)g d=1∑ndxkA(⌊dn⌋)g∣d∑μ(gd)is(g)g
Then make B ( d ) = d x k ∑ g ∣ d μ ( d g ) i s ( g ) g B(d)=d^{xk}\sum_{g|d}\mu(\frac{d}{g})is(g)g B(d)=dxk∑g∣dμ(gd)is(g)g, It can be o ( n l o g n ) o(nlogn) o(nlogn) Pretreated , The formula finally becomes ,
∑ d = 1 n A ( ⌊ n d ⌋ ) B ( d ) \sum_{d=1}^{n}A(\lfloor \frac{n}{d} \rfloor)B(d) d=1∑nA(⌊dn⌋)B(d)
ah ! Isn't this some obvious number theory block .
So we just need to preprocess out B ( d ) B(d) B(d) And S B ( d ) SB(d) SB(d), Then preprocess out A ( d ) A(d) A(d), Then the number theory is divided into blocks .
The code constant is huge .
Code :
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll MAXN=400005;
ll fpow(ll a,ll n)
{
ll sum=1,base=a%mod;
while(n!=0)
{
if(n%2)sum=sum*base%mod;
base=base*base%mod;
n/=2;
}
return sum;
}
ll inv(ll a)
{
return fpow(a,mod-2);
}
ll prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(ll n)
{
notPrime[1]=mu[1]=1;
for(ll i=2;i<=n;i++)
{
if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
for(ll j=0;j<tot&&i*prime[j]<=n;j++)
{
notPrime[i*prime[j]]=1;
if(i%prime[j])mu[i*prime[j]]=-mu[i];
else {
mu[i*prime[j]]=0;break;}
}
}
}
ll T,k,x,n;
ll A[400005];
ll is[400005];
ll B[400005];
ll SB[400005];
int main()
{
scanf("%lld%lld%lld",&T,&k,&x);
initMu(200000);
for(ll i=2;i*i<=200000;i++)
{
for(ll j=1;i*i*j<=200000;j++)is[i*i*j]=1;
}
for(ll g=1;g<=200000;g++)
{
for(ll d=g;d<=200000;d+=g)
{
B[d]=(B[d]+g*mu[d/g]*(1-is[g])%mod)%mod;
}
}
for(ll d=1;d<=200000;d++)B[d]=B[d]*fpow(d,x*k)%mod;
for(ll d=1;d<=200000;d++)SB[d]=(SB[d-1]+B[d])%mod;
for(ll d=1;d<=200000;d++)
{
A[d]=(A[d-1]+fpow(d,k))%mod;
}
for(ll d=1;d<=200000;d++)A[d]=fpow(A[d],x);
while(T--)
{
scanf("%lld",&n);
ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
if(n/l)r=n/(n/l);
else r=n;
r=min(r,n);
ans=(ans+A[n/l]*(SB[r]-SB[l-1])%mod)%mod;
}
ans=ans%mod;
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425210.html
边栏推荐
- ABAP 7.4 SQL Window Expression
- Flink 流批一体在小米的实践
- Two methods of building Yum source warehouse locally
- JS scope, scope chain, global variables and local variables
- (Extended) bsgs and higher order congruence equation
- C语言:表达式求值(整型提升、算术转换 ...)
- Redis exception read error on connection solution
- ALV tree (ll LR RL RR) insert delete
- 面试官:说几个PHP常用函数,幸好我面试之前看到了这篇文章
- DVWA range practice
猜你喜欢
Leetcode题库78. 子集(递归 c实现)
npm ERR! network
Solving Lucas number and combination theorem
SAP 03-amdp CDs table function using 'with' clause
Alibaba cloud architects interpret the four mainstream game architectures
PHP notes (I): development environment configuration
JS what is an event? Event three elements and operation elements
《信息系统项目管理师总结》第八章 项目干系人管理
AQS & reentrantlock implementation principle
Kettle实验 (三)
随机推荐
The sap export excel file opens and shows that the file format and extension of "XXX" do not match. The file may be damaged or unsafe. Do not open it unless you trust its source. Do you still want to
Flink 流批一体在小米的实践
Flutter 的加载动画这么玩更有趣
Kettle实验 转换案例
SAP excel has completed file level validation and repair. Some parts of this workbook may have been repaired or discarded.
STM32 and FreeRTOS stack parsing
Chinese Remainder Theorem and extended Chinese remainder theorem that can be understood by Aunt Baojie
Cloud identity is too loose, opening the door for attackers
《數字電子技術基礎》3.1 門電路概述、3.2 半導體二極管門電路
Redis 过期 key 清理删除策略汇总
JS prototype chain
Cloud computing competition -- basic part of 2020 competition [task 3]
Your guide to lowering your cholesterol with TLC (continuously updated)
Set the maximum width of the body, but why does the background color of the body cover the whole page?
SQL used query statements
Exclusive thoughts and cases of JS
Number of islands
Setnx command execution failed due to full redis memory
Summary of wrong questions 1
JS DOM event