Skip to content

11396: 【原1396】数学题1

题目

题目描述

author: SamJia 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1396

题目描述

现在有一方程: 2x+3y+5z=n,n是已知整数,x,y,z均非负,求方程有多少组解。

输入格式

第一行有一个整数m,代表测试点数目,m<=100。

接下来m行每行一个整数,代表方程中的n,0<=n<=2000000。

输出格式

每个测试点有一个输出,即方程解的组数。

Sample Input

2
0
9

Sample Output

1
3

Hint

long long

yyong119's solution

#include <cstdio>
#define MAX_N 2000005
using namespace std;
int m, x;
long long ans[MAX_N];
int main() {
    for (register int n = 0; n < 100; ++n) {
        for (register int x = 0; x * 2 <= n; ++x)
            for (register int y = 0; x * 2 + y * 3 <= n; ++y)
                if ((n - x * 2 - y * 3) % 5 == 0) ++ans[n];
        // printf("n = %d ans = %d ", n, ans[n]);
        // if (n >= 10)
        //     printf("delta=%d", ans[n] - ans[n - 10]);
        // printf("\n");
    }
    for (register int i = 20; i < MAX_N; ++i)
        ans[i] = ans[i - 10] + ((i + 1) / 3);
    // for (register int i = 20; i < 100; ++i)
    //     printf("n = %d ans = %d\n", i, ans[i]);
    // printf("%lld %lld %lld\n", ans[90], ans[95], ans[99]);
    // printf("%lld %lld\n", ans[95], ans[99]);
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &x);
        printf("%lld\n", ans[x]);
    }
    return 0;
}