# JZOJ – 5813 计算

Time Limit : 1000ms
Memory Limit : 512MB

## Sample Input

### Case 1

6 1


### Case 2

6 3


## Sample Output

### Case 1

10


### Case 2

2248


## 解题思路

$f[i][j] = \sum_{t=1}^{k_i} f[i-1][j-t]$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 20 + 10;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9'){
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

inline long long exgcd(long long a, long long b, long long &x, long long &y){
if(b == 0){
x = 1;
y = 0;
return a;
}else{
long long d = exgcd(b, a%b, y, x);
y -= x * (a / b);
return d;
}
}

inline long long gcd(long long a, long long b){
if(b == 0)
return a;
return gcd(b, a%b);
}

inline long long lcm(long long a, long long b){
if(!a)
return b;
if(!b)
return a;

return a / gcd(a, b) * b;
}

int data[MAXN];
int n, m;
long long ans;

inline void solve(int x, long long a, long long b, int k){
if(a > n || b > n)
return;

if(x == m + 1){
if(!a || !b)
return;

long long x, y;
long long d = exgcd(a, b, x, y);

if(d != 1)
return;

x %= b;

while(x <= 0)
x += b;

if(k%2 == 0)
ans += (n/a - x + b) / b;
else
ans -= (n/a - x + b) / b;

return;
}

solve(x+1, lcm(a, data[x]), b, k+1);
solve(x+1, a, lcm(b, data[x]), k+1);
solve(x+1, a, b, k);
}

int main(){

freopen("sazetak.in", "r", stdin);
freopen("sazetak.out", "w", stdout);