E 洛谷 P3598 Koishi Loves Number Theory[数论]

时间:2023-08-25 20:46:44

题目描述

Koishi十分喜欢数论。

她的朋友Flandre为了检测她和数论是不是真爱,给了她一个问题。

已知E 洛谷 P3598 Koishi Loves Number Theory[数论]

给定E 洛谷 P3598 Koishi Loves Number Theory[数论]E 洛谷 P3598 Koishi Loves Number Theory[数论]个数E 洛谷 P3598 Koishi Loves Number Theory[数论],求E 洛谷 P3598 Koishi Loves Number Theory[数论]E 洛谷 P3598 Koishi Loves Number Theory[数论]取模。

按照套路,呆萌的Koishi当然假装不会做了,于是她来向你请教这个问题,希望你能在E 洛谷 P3598 Koishi Loves Number Theory[数论]秒内给她答案。

输入输出格式

输入格式:

第一行包含两个整数E 洛谷 P3598 Koishi Loves Number Theory[数论]E 洛谷 P3598 Koishi Loves Number Theory[数论],接下来一行E 洛谷 P3598 Koishi Loves Number Theory[数论]个整数表示E 洛谷 P3598 Koishi Loves Number Theory[数论]

输出格式:

一个整数,表示答案

输入输出样例

输入样例#1:
3 5
1 2 4 5 0
输出样例#1:
44044

说明

E 洛谷 P3598 Koishi Loves Number Theory[数论]表示若干个数的最小公倍数

对于10%的数据:E 洛谷 P3598 Koishi Loves Number Theory[数论]

对于另外20%的数据:E 洛谷 P3598 Koishi Loves Number Theory[数论]

对于另外30%的数据:E 洛谷 P3598 Koishi Loves Number Theory[数论]

对于另外40%的数据:E 洛谷 P3598 Koishi Loves Number Theory[数论]


标解:

先列两个结论

  • E 洛谷 P3598 Koishi Loves Number Theory[数论]

  • E 洛谷 P3598 Koishi Loves Number Theory[数论]

结论1可以考虑辗转相除法证明,结论2可以考虑lcm的积性求质因子贡献,这里不详细展开。

E 洛谷 P3598 Koishi Loves Number Theory[数论] 的范围很大,但它们的 E 洛谷 P3598 Koishi Loves Number Theory[数论] 数量很少。开一个map维护每个gcd和它的贡献就没了啊。

这两个结论怎么想出来啊啊啊啊

实现上好难,去请教了WerkeyTom_FTD %%%

就是用个map维护a的每个gcd出现的次数(上-下),加入一个数时,(a[i]+1)++,用a[i]+1与当前map里的gcd求gcd,次数取反就行了,然后更新答案

这里的x很大,所以一读入先%MOD;WerkeyTom_FTD还提到有可能x-1在MOD意义下没有逆元,可以先全乘MOD然后再做

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
const int N=,MOD=1e9+;
inline ll read(){
char c=getchar();ll x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
ll x,n,a[N];
inline ll gcd(ll a,ll b){return b==?a:gcd(b,a%b);}
map<ll,ll> mp,t;
map<ll,ll>::iterator it;
ll Pow(ll a,ll b){
ll ans=;
for(;b;b>>=,a=a*a%MOD)
if(b&) ans=ans*a%MOD;
return ans;
}
ll Inv(ll a){return Pow(a,MOD-);}
ll ans=;
void solve(){
for(int i=;i<=n;i++){ //printf("hi %d %d\n",i,a[i]);
t[a[i]]++;
ans=ans*(Pow(x,a[i])-)%MOD;//printf("ans %lld\n",ans);
for(it=mp.begin();it!=mp.end();it++){
ll _x=it->first,_y=it->second;
t[_x]+=_y;
ll nx=gcd(_x,a[i]),ny=-_y;
//printf("lala %d %d %d %d\n",_x,_y,nx,ny);
t[nx]+=ny;
if(ny>) ans=ans*Pow( Pow(x,nx)-, ny)%MOD;
else ans=ans*Pow( Inv(Pow(x,nx)-), -ny)%MOD;
//printf("ans %lld\n",ans);
}
swap(mp,t);t.clear();
}
ans=ans*Inv(x-)%MOD;
printf("%lld\n",ans);
}
int main(int argc, const char * argv[]) {
x=read()%MOD;n=read();
for(int i=;i<=n;i++) a[i]=read()+;
solve();
return ;
}