题目描述
Koishi十分喜欢数论。
她的朋友Flandre为了检测她和数论是不是真爱,给了她一个问题。
已知
给定和个数,求对取模。
按照套路,呆萌的Koishi当然假装不会做了,于是她来向你请教这个问题,希望你能在秒内给她答案。
输入输出格式
输入格式:
第一行包含两个整数和,接下来一行个整数表示。
输出格式:
一个整数,表示答案
输入输出样例
输入样例#1:
3 5
1 2 4 5 0
输出样例#1:
44044
说明
表示若干个数的最小公倍数
对于10%的数据:
对于另外20%的数据:
对于另外30%的数据:
对于另外40%的数据:
标解:
先列两个结论
结论1可以考虑辗转相除法证明,结论2可以考虑lcm的积性求质因子贡献,这里不详细展开。
的范围很大,但它们的 数量很少。开一个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 ;
}