7-4 好数 暴力

一个正整数若能写成ax+by+cz ( x, y, z 为非负整数，a,b,c均为正数）形式，则称它为“好数”。则集合{1,2,… ,n}中好数的个数有多少?(a=20,b=8,c=27,n=200,为2020年全国高中数学联赛（浙江赛区）初赛试题填空第9题) 输入格式:

输入四个正数a,b,c,n（n<=2000）。 输出格式:

一个数，表示好数的个数。 输入样例:

20 8 27 200

输出样例:

153

数据量较小,可以直接枚举1到n判断每个数字是不是好数,每个好数O(n^2枚举x和y,z可以算出来 总的时间复杂度$O(n^3)$

#define debug #ifdef debug #include <time.h> #include "/home/majiao/mb.h" #endif #include <iostream> #include <algorithm> #include <vector> #include <string.h> #include <map> #include <set> #include <stack> #include <queue> #include <math.h> #define MAXN ((int)1e5+7) #define ll long long #define INF (0x7f7f7f7f) #define fori(lef, rig) for(int i=lef; i<=rig; i++) #define forj(lef, rig) for(int j=lef; j<=rig; j++) #define fork(lef, rig) for(int k=lef; k<=rig; k++) #define QAQ (0) using namespace std; #define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0) void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... A> void err(T a, A... x) { cout << a << ' '; err(x...); } namespace FastIO { char print_f[105]; void read() { } void print() { putchar('\n'); } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { x = 0; char ch = getchar(); ll f = 1; while (!isdigit(ch)) { if (ch == '-') f *= -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; read(oth...); } template <typename T, typename... T2> inline void print(T x, T2... oth) { ll p3=-1; if(x<0) putchar('-'), x=-x; do{ print_f[++p3] = x%10 + 48; } while(x/=10); while(p3>=0) putchar(print_f[p3--]); putchar(' '); print(oth...); } } // namespace FastIO using FastIO::print; using FastIO::read; int n, m, Q, K; int main() { #ifdef debug freopen("test", "r", stdin); // freopen("out_main", "w", stdout); clock_t stime = clock(); #endif int a, b, c; read(a, b, c, n); int ans = 0; set<int> seta; for(int i=1; i<=n; i++) { int x, y; for( x=0; x*a<=i; x++) { int sec = i - x * a; for( y=0; y*b<=sec; y++) { int thd = sec - y * b; if(thd % c == 0) { seta.insert(i); } } } } printf("%d\n", int(seta.size())); #ifdef debug clock_t etime = clock(); printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC); #endif return 0; }