【数论|BZOJ 3560 DZY Loves Math V 数论】题目大意：给定a1,a2,...,an,求
由于φ是积性函数，我们可以将i1i2...in分解质因数，对于每个质因数分开讨论，求积即可
将每个a分解质因数，假设分解后某个质数p在每个ai中的次数分别是bi，那么p对答案的贡献就是
文章图片
于是对p^j维护一个前缀和，直接计算即可
#include
#include
#include
#include
#define MOD 1000000007
using namespace std;
struct abcd{
int p,a;
bool operator < (const abcd &x) const
{
if(p!=x.p)
return p>=1;
}
return re;
}
void Calculate(int l,int r)
{
static long long sum[30];
long long p=prime_factors[l].p;
long long re=1;
int i;
sum[0]=1;
for(i=1;
i<=prime_factors[r].a;
i++)
sum[i]=sum[i-1]*p%MOD;
for(i=1;
i<=prime_factors[r].a;
i++)
(sum[i]+=sum[i-1])%=MOD;
for(i=l;
i<=r;
i++)
(re*=sum[prime_factors[i].a])%=MOD;
re--;
(re*=Quick_Power(p,MOD-2))%=MOD;
(re*=p-1,++re)%=MOD;
(ans*=re)%=MOD;
}
int main()
{
int i,x;
cin>>n;
for(i=1;
i<=n;
i++)
{
scanf("%d",&x);
Decomposition(x);
}
sort(prime_factors+1,prime_factors+tot+1);
for(i=1;
i<=tot;
i++)
{
static int last;
if(i==tot||prime_factors[i].p!=prime_factors[i+1].p)
Calculate(last+1,i),last=i;
}
cout<<(ans%MOD+MOD)%MOD< 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- bzoj|Bzoj3817:Sum
- HDU 5528 Count a × b
- 线性同余方程组