#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define ft first
#define sd second
#define MP make_pair
using namespace std;
typedef long long ll;
const int M = 10;
const ll MX = ll(2e9);
ll ans = 0, n, m, a[M];
ll lcm(ll x, ll y){
return min(MX, x * y / __gcd(x, y));
}
pll inv(ll a, ll b){
if (a == 0)
return MP(0, 1);
else {
pll old = inv(b % a, a);
return MP(old.sd - (b / a) * old.ft, old.ft);
}
}
pll calc(ll fi, ll se){
if (__gcd(fi, se) > 1) return MP(-1, -1);
ll ap = inv(fi, se).sd;
ap %= fi;
if (ap < 0) ap += fi;
return MP(ap * se, fi * se);
}
void rec(int nm, ll fi, ll se, ll par){
if (nm == m){
if (fi == 1 || se == 1) return;
pll res = calc(fi, se);
if (res.ft < 0) return;
if (n - 1 < res.ft) return;
ans += par * ((n - 1 - res.ft) / res.sd + 1);
return;
}
rec(nm + 1, fi, se, par);
rec(nm + 1, lcm(fi, a[nm]), se, -par);
rec(nm + 1, fi, lcm(se, a[nm]), -par);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
if ((n - 1) % a[i] == 0)
ans = 1;
rec(0, 1, 1, 1);
cout << ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
7 ms |
384 KB |
Output is correct |
10 |
Correct |
8 ms |
384 KB |
Output is correct |