卧薪尝胆,厚积薄发。
HNOI2002 跳蚤
Date: Sat Oct 20 15:36:32 CST 2018
In Category:
NoCategory
Description:
有
$n+1$
张卡片,每张都在
$[1,m]$
之间,且第
$n+1$
张是
$m$
,随机
$n+1$
张卡片,有
$m^n$
种不同的方案,求有多少个方案,满足可以线性组合出
$1$
。
$1\leqslant n,m\leqslant 10^8$
Solution:
首先由裴蜀定理得要求的等价于:
$$
\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_3=1}^m[\gcd(i_1,i_2,\dots,i_n)=1]
$$
正难则反,考虑求
$\gcd$
不为
$1$
的序列数。
然后我们把
$m$
分解质因数,设其中一个质数是
$p_i$
,那么
$\gcd$
是
$p_i$
的倍数的序列数为
$(\frac m {p_i})^n$
,大概就是每个数都必须是
$p_i$
的倍数,这样的数在
$[1,m]$
中有
$\frac m {p_i}$
个。
肯定会算重,容斥一下就好了。
Code:
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n,m;
int pri[100000010],tot = 0;
void divide(int k)
{
int s = k;
for(int i = 2;i * i <= k;++i)
{
if(s % i == 0)
{
pri[++tot] = i;
while(s % i == 0)s /= i;
}
}
if(s != 1)pri[++tot] = s;
return;
}
typedef long long ll;
ll ans = 0;
ll power(ll a,int b)
{
ll res = 1;
while(b > 0)
{
if(b & 1)res = res * a;
a = a * a;
b = b >> 1;
}
return res;
}
void calc(int pos,int type,ll val)
{
if(val > m)return;
if(pos == tot + 1)
{
ans += type * power(m / val,n);
return;
}
calc(pos + 1,type,val);
calc(pos + 1,-type,val * pri[pos]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
divide(m);
calc(1,1,1);
cout << ans << endl;
return 0;
}
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡