A Odd Set

题目大意

给一个数n，给2*n个数，将他们分为n组，每组两个数，问能否使每组数的和为奇数

主要思路

只有奇数+偶数=奇数，那么只有当奇数个数==偶数个数时才能凑成

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. const int N = 200010;
  20. int n, a[N];
  22. signed main(void)
  23. {
  24.     int T;
  25.     cin >> T;
  26.     while(T--)
  27.     {
  28.         int odd = 0, even = 0;
  29.         cin >> n;
  30.         for(int i = 0; i < 2 * n; i++)
  31.         {
  32.             int t;
  33.             cin >> t;
  34.             if(t % 2) odd++;
  35.             else even++;
  36.         }
  37.         if(odd == even) puts("Yes");
  38.         else puts("No");
  39.     }
  40.     return 0;
  41. }

B Plus and Multiply

题目大意

给定一个数a, 一个数b，同时还有一个从1开始的数列，数列无限长，数列中的数可以从数列中任选一个数乘a或者加b来添加，问给你一个数n，这个数是否在这个数列中

主要思路

假定一个数x = ((1 + b) a + b + b)) a + b = (1 + b) a a + (2a + 1)b = a _ a + (a^2 + 2_a + 1) * b，也就是说任意一个在数列中的数，一定通过可以减去几个a来让这个数成为b的倍数，所以可以通过将给定的数n通过减0个a, 1个a…判断每个数是否是b的倍数即可

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. signed main(void)
  20. {
  21.     int T;
  22.     cin >> T;
  23.     while(T--)
  24.     {
  25.         int n, a, b;
  26.         cin >> n >> a >> b;
  27.         bool flag = false;
  28.         for(int i = 1; i <= n; i *= a)
  29.         {
  30.             if((n - i) % b == 0)
  31.             {
  32.                 flag = true;
  33.             }
  34.             if(a == 1) break;
  35.         }
  36.         if(flag) puts("Yes");
  37.         else puts("No");
  38.     }
  39.     return 0;
  40. }

C Strange Function

题目大意

定义一个f(x)为x%i不等于0的最小正整数i，给定一个数n，求f(1) + f(2) + …+ f(n)的和

主要思路

首先我们考虑f(x)的取值最大为41，为42时说明x是141的最小公倍数为219060189739591200，大于n的取值范围。

其次我们考虑2~41每个值对答案的贡献，所有奇数答案都为2，偶数答案一定大于2，每个数的贡献至少为2，所以我们先把答案初始化为n*2。

2比较特殊考虑完毕，如果f(x)想要有3~41中某个数i的贡献，那么x一定为1 ~ i - 1的最小公倍数的倍数，统计比n小的中有多少数是1 ~ i - 1的最小公倍数的倍数就相当于n / lcm(1 ~ i - 1), 这个数的含义是有多少数的f(x)至少能取到i，如果至少能取到i那么对答案贡献+1，所以3~41中某个数i的贡献为n / lcm(1 ~ i - 1)

AC代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. #include <map>
  11. using namespace std;
  13. #define int long long
  14. #define debug(a) cout << #a << " = " << a << endl;
  15. #define x first
  16. #define y second
  17. typedef pair<int, int> P;
  19. int gcd(int a, int b)
  20. {
  21.     return b ? gcd(b, a % b) : a;
  22. }
  24. const int N = 50, mod = 1000000007;
  25. int a[N];
  27. signed main(void)
  28. {
  29.     int x = 2;
  30.     for(int i = 1; i <= 42; i++)
  31.     {
  32.         a[i] = x;
  34.         x = x * i / gcd(x, i);
  35.     }
  36.     cout << a[42] << endl;
  37.     int T;
  38.     cin >> T;
  39.     while(T--)
  40.     {
  41.         int n;
  42.         cin >> n;
  43.         int ans = n * 2;
  44.         for(int i = 3; i <= 41; i++) ans = (ans + n / a[i]) % mod;
  45.         cout << ans << endl;
  46.     }
  47.     return 0;
  48. }