生活随笔
收集整理的這篇文章主要介紹了
2021牛客暑期多校训练营4 H-Convolution（数学）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
H-Convolution
x?y=xygcd?(x,y)x\bigotimes y=\frac{xy}{\gcd(x,y)}x?y=gcd(x,y)xy?
下面大佬題解推🦁
Ultraman-Ace題解
#include<bits/stdc++.h>
using namespace std
;
using ll
=long long;
template <class T=int> T
rd()
{T res
=0;T fg
=1;char ch
=getchar();while(!isdigit(ch
)) {if(ch
=='-') fg
=-1;ch
=getchar();}while( isdigit(ch
)) res
=(res
<<1)+(res
<<3)+(ch
^48),ch
=getchar();return res
*fg
;
}
const ll mod
=998244353;
ll
qmi(ll a
,ll b
)
{ll v
=1;while(b
){if(b
&1) v
=v
*a
%mod
;b
>>=1;a
=a
*a
%mod
;}return v
;
}
const int N
=1000010;
ll n
,c
;
ll a
[N
],b
[N
];
ll pw
[N
],sum
[N
];
int main()
{n
=rd
<ll
>(),c
=rd
<ll
>();for(int i
=1;i
<=n
;i
++) a
[i
]=rd
<ll
>();for(int i
=1;i
<=n
;i
++) pw
[i
]=qmi(i
,c
);for(int i
=1;i
<=n
;i
++){for(int j
=1;i
*j
<=n
;j
++)sum
[j
]=(sum
[j
-1]+a
[i
*j
]*pw
[j
]%mod
)%mod
;for(int j
=1;i
*j
<=n
;j
++)if(__gcd(i
,j
)==1) {int u
=n
/max(i
,j
);b
[i
*j
]=(b
[i
*j
]+sum
[u
]*pw
[j
]%mod
)%mod
;}}ll ans
=0;for(int i
=1;i
<=n
;i
++) ans
^=b
[i
];printf("%lld\n",ans
);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2021牛客暑期多校训练营4 H-Convolution（数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
