# Solution
Date: 4/12/2024

## Bài 1:

Ta thấy, số lượng số không chia hết cho các số từ 2 đến 10 chính là n trừ đi các số chia hết cho từ 2 đến 10. Nhưng khi trừ chúng ta cần chú ý đến việc các số có thể bị lặp lại.

Code:

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{  
   long long s,n;
   cin>>n;
   s=n-n/2-n/3-n/7-n/5+n/6+n/14+n/10+n/21+n/35+n/15-n/42-n/70-n/30-n/105+n/210;

   cout<<s;

    return 0;
}

## Bài 2
Quy tắc mã hóa:
Từ chuỗi ban đầu , mỗi thao tác tạo ra một chuỗi mới bằng cách:
- Xóa ký tự đầu hoặc cuối của để tạo chuỗi con .
- Ghép vào đầu hoặc cuối của .
Bài toán đòi hỏi đếm số cách khác nhau có thể tạo chuỗi từ theo quy tắc trên.

Bài này ta có thể sử dụng quay lui hặc dp để giải quyết

Code (Quay lui)

#include <bits/stdc++.h>
using namespace std;

int xl(string s)
{
   if(s.size()==1 || s.size()%2==0)
      return 0;
   string s1=s.substr(0,s.size()/2+1);
   string s2=s1.substr(0,s1.size()-1);
   string s3=s1.substr(1,s1.size()-1);
   int t=0;
   if(s1+s2==s || s1+s3==s)
   {
      t=xl(s1)+1;
      if(s1+s2==s && s1+s3==s)
         t=t*2;
   }
   s1=s.substr(s.size()/2,s.size()/2+1);
   s2=s1.substr(0,s1.size()-1);
   s3=s1.substr(1,s1.size()-1);
   int v=0;
   if(s2+s1==s || s3+s1==s)
   {
      v=xl(s1)+1;
      if(s1+s2==s && s1+s3==s)
         v=v*2;
   }
   return t+v;
}
int main()
{
   string s;
   cin>>s;
   int n=s.size();
   int t=xl(s);
   cout<<t;
}

## Bài 3
Cách chậm:
Ta tìm cách duyệt n và m và đếm cặp n và m thoả mãn số lượng hình vuông chứa trong bảng nxm bằng x.=> Tìm cách duyệt n và m đến mức tối đa.

Cách tối ưu:
Tìm cách thu hẹp giá trị của n và m khi duyệt.
Ta giả sử số hàng nhỏ hơn số cột, n <= m, việc giả sử này giúp ích cho việc ta tránh tính hình vuông 2 lần. Nếu n > m thì ta chỉ việc hoán đổi 2 giá trị n và m cho lẫn nhau. Ta sẽ tính toán giá trị của x, để tìm cách thu hẹp giá trị của n và m khi duyệt. x sẽ được tính như sau:

$$
x = n \cdot m + (n-1) \cdot (m-1) + (n-2) \cdot (m-2) + \ldots + 1 \cdot (m-(n-1))
$$

$$
\Leftrightarrow x = \sum_{i=0}^{n-1} (n-i)(m-i)
$$

$$
\Leftrightarrow x = \sum_{i=0}^{n-1} (n \cdot m - i(n+m) + i^2)
$$

$$
x = n^2 \cdot m - (n+m) \sum_{i=0}^{n-1} i + \sum_{i=0}^{n-1} i^2
$$

$$
\text{Khi đó, } x = n^2 \cdot m - \frac{(n+m)(n-1)n}{2} + \frac{(n-1)n(2n-1)}{6}
$$

$$
1 + 2 + \ldots + n = \frac{(n+1)n}{2} \quad
$$

$$
1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}
$$

---

$$
\text{Hay } 6x = 3 \cdot m \cdot n^2 + 3 \cdot m \cdot n - n^3 + n
$$

Do n <= m, nên:

$$
6x = 3 \cdot m \cdot n^2 + 3 \cdot m \cdot n - n^3 + n \geq 3n^3 + 3n^2 - n^3 + n = 2n^3 + 3n^2 + n
$$

Hay:

$$
2n^3 \leq 6x \Leftrightarrow n \leq \sqrt[3]{3x}
$$

---

Độ phức tạp của thuật toán là:
$$
O(\sqrt[3]{x})
$$

Code:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;

int main() {
	ll x;
	int k = 0, d = 0;
	vll N, M;
	scanf("%lld", &x);
	for (ll m = 1; m * (m + 1) / 2 * (2 * m + 1) / 3 <= x; m++) {
		if ((6 * x) % (m * (m + 1)) == 0 && ((6 * x) / (m * (m + 1)) + m - 1) % 3 == 0) {
			M.push_back(m);
			N.push_back(((6 * x) / (m * (m + 1)) + m - 1) / 3);
			k++;
		}
	}
	if (M[k - 1] == N[k - 1]) d = 1;
	printf("%d\n", 2 * k - d);
	for (int i = 0; i < k; i++) printf("%lld %lld\n", M[i], N[i]);
	for (int i = d; i < k; i++) printf("%lld %lld\n", N[k - i - 1], M[k - i - 1]);
}
}