Các solution cho contest basic2_en
Last active
September 10, 2016 10:30
-
-
Save ngobach/d04aed2cfeb26c7141346f4d2fd6fa7f to your computer and use it in GitHub Desktop.
00_basic2_en.md
Bài này yêu cầu đếm số chữ số 0 sau cùng của n giai thừa (n!).
Để tính số được số chữ số 0 phía sau của n! ta cần đưa số n! về dạng 2m5nk. Vì với mỗi số 2 và số 5 khi kết hợp sẽ tạo ra 1 số 0 ở phía cuối.
Mà n! = 1*2*3*...*(n-1)*n. Nên m sẽ lớn hơn n rất nhiều, ta chỉ cần tìm n để tính.
Xét trong khoảng từ [1,n] có những số nào khi nhân vào sẽ tạo ra thêm 1 phần tử 5. Giả sử với n = 24 sẽ có 5,10,15,20. Vậy là có 4 số là bội của 5. => 24! sẽ có 4 chữ số 0 phía sau.
Xét trường hợp khác với n = 26 thì sẽ thấy 25 = 5*5, khi nhân vào sẽ tạo ra 2 phần tử 5. Tương tự với 50, 75, 100. Và lớn hơn khi n = 126 thì khi nhân 125 sẽ tạo ra 3 số 5. => Cần phải xét riêng các lũy thừa của 5.
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n,l,res;
cin >> n;
while (n--) {
cin >> l;
res = 0;
for (LL t=5;t<=l;t*=5) res += l/t;
cout << res << '\n';
}
}Bài này giúp làm quen khi làm việc với số lớn. Không thể dùng được các kiểu dữ liệu có sẵn như long long. Ở đây mình chỉ implements phép toán nhân thôi nên tự code cho nhanh. Nếu cần nhiều phép toán hơn có thể tham khảo lớp big int trong CodeSuite.
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,t,A[1000],m, k;
cin >> t;
while (t--) {
cin >> n;
memset(A,0,sizeof(A));
A[0] = 1;
m = 0; // Nho'
k = 1; // SO luong chu so
_for(i,2,n+1) {
_for(j,0,k) {
m += A[j]*i;
A[j] = m%10;
m /= 10;
}
while (m) {
A[k++] = m%10;
m /= 10;
}
}
_for(i,k-1,-1) {
cout << A[i];
}
cout << '\n';
}
}Chỉ là tính toán. Vấn đề là số ở đây lớn. Cần thực hiện phép cộng và trừ. Có thể xảy ra số âm. Ở đây mình dùng luôn lớp big int. Đã chia sẻ với các bạn.
Xem tại ĐÂY
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int base = 1000000000;
const int base_digits = 9;
struct bigint {
vector<int> a; int sign;
bigint() :
sign(1) {
}
bigint(long long v) {
*this = v;
}
bigint(const string &s) {
read(s);
}
void operator=(const bigint &v) {
sign = v.sign;
a = v.a;
}
void operator=(long long v) {
sign = 1;
if (v < 0)
sign = -1, v = -v;
for (; v > 0; v = v / base)
a.push_back(v % base);
}
bigint operator+(const bigint &v) const {
if (sign == v.sign) {
bigint res = v;
for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
if (i == (int) res.a.size())
res.a.push_back(0);
res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
carry = res.a[i] >= base;
if (carry)
res.a[i] -= base;
}
return res;
}
return *this - (-v);
}
bigint operator-(const bigint &v) const {
if (sign == v.sign) {
if (abs() >= v.abs()) {
bigint res = *this;
for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
carry = res.a[i] < 0;
if (carry)
res.a[i] += base;
}
res.trim();
return res;
}
return -(v - *this);
}
return *this + (-v);
}
void operator*=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
if (i == (int) a.size())
a.push_back(0);
long long cur = a[i] * (long long) v + carry;
carry = (int) (cur / base);
a[i] = (int) (cur % base);
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
}
bigint operator*(int v) const {
bigint res = *this;
res *= v;
return res;
}
friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
int norm = base / (b1.a.back() + 1);
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize(a.a.size());
for (int i = a.a.size() - 1; i >= 0; i--) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ((long long) base * s1 + s2) / b.a.back();
r -= b * d;
while (r < 0)
r += b, --d;
q.a[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair(q, r / norm);
}
bigint operator/(const bigint &v) const {
return divmod(*this, v).first;
}
bigint operator%(const bigint &v) const {
return divmod(*this, v).second;
}
void operator/=(int v) {
if (v < 0)
sign = -sign, v = -v;
for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
long long cur = a[i] + rem * (long long) base;
a[i] = (int) (cur / v);
rem = (int) (cur % v);
}
trim();
}
bigint operator/(int v) const {
bigint res = *this;
res /= v;
return res;
}
int operator%(int v) const {
if (v < 0)
v = -v;
int m = 0;
for (int i = a.size() - 1; i >= 0; --i)
m = (a[i] + m * (long long) base) % v;
return m * sign;
}
void operator+=(const bigint &v) {
*this = *this + v;
}
void operator-=(const bigint &v) {
*this = *this - v;
}
void operator*=(const bigint &v) {
*this = *this * v;
}
void operator/=(const bigint &v) {
*this = *this / v;
}
bool operator<(const bigint &v) const {
if (sign != v.sign)
return sign < v.sign;
if (a.size() != v.a.size())
return a.size() * sign < v.a.size() * v.sign;
for (int i = a.size() - 1; i >= 0; i--)
if (a[i] != v.a[i])
return a[i] * sign < v.a[i] * sign;
return false;
}
bool operator>(const bigint &v) const {
return v < *this;
}
bool operator<=(const bigint &v) const {
return !(v < *this);
}
bool operator>=(const bigint &v) const {
return !(*this < v);
}
bool operator==(const bigint &v) const {
return !(*this < v) && !(v < *this);
}
bool operator!=(const bigint &v) const {
return *this < v || v < *this;
}
void trim() {
while (!a.empty() && !a.back())
a.pop_back();
if (a.empty())
sign = 1;
}
bool isZero() const {
return a.empty() || (a.size() == 1 && !a[0]);
}
bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}
bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}
long long longValue() const {
long long res = 0;
for (int i = a.size() - 1; i >= 0; i--)
res = res * base + a[i];
return res * sign;
}
friend bigint gcd(const bigint &a, const bigint &b) {
return b.isZero() ? a : gcd(b, a % b);
}
friend bigint lcm(const bigint &a, const bigint &b) {
return a / gcd(a, b) * b;
}
void read(const string &s) {
sign = 1;
a.clear();
int pos = 0;
while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
if (s[pos] == '-')
sign = -sign;
++pos;
}
for (int i = s.size() - 1; i >= pos; i -= base_digits) {
int x = 0;
for (int j = max(pos, i - base_digits + 1); j <= i; j++)
x = x * 10 + s[j] - '0';
a.push_back(x);
}
trim();
}
friend istream& operator>>(istream &stream, bigint &v) {
string s;
stream >> s;
v.read(s);
return stream;
}
friend ostream& operator<<(ostream &stream, const bigint &v) {
if (v.sign == -1)
stream << '-';
stream << (v.a.empty() ? 0 : v.a.back());
for (int i = (int) v.a.size() - 2; i >= 0; --i)
stream << setw(base_digits) << setfill('0') << v.a[i];
return stream;
}
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
vector<long long> p(max(old_digits, new_digits) + 1);
p[0] = 1;
for (int i = 1; i < (int) p.size(); i++)
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (int i = 0; i < (int) a.size(); i++) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.push_back(int(cur % p[new_digits]));
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back((int) cur);
while (!res.empty() && !res.back())
res.pop_back();
return res;
}
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll &a, const vll &b) {
int n = a.size();
vll res(n + n);
if (n <= 32) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res[i + j] += a[i] * b[j];
return res;
}
int k = n >> 1;
vll a1(a.begin(), a.begin() + k);
vll a2(a.begin() + k, a.end());
vll b1(b.begin(), b.begin() + k);
vll b2(b.begin() + k, b.end());
vll a1b1 = karatsubaMultiply(a1, b1);
vll a2b2 = karatsubaMultiply(a2, b2);
for (int i = 0; i < k; i++)
a2[i] += a1[i];
for (int i = 0; i < k; i++)
b2[i] += b1[i];
vll r = karatsubaMultiply(a2, b2);
for (int i = 0; i < (int) a1b1.size(); i++)
r[i] -= a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
r[i] -= a2b2[i];
for (int i = 0; i < (int) r.size(); i++)
res[i + k] += r[i];
for (int i = 0; i < (int) a1b1.size(); i++)
res[i] += a1b1[i];
for (int i = 0; i < (int) a2b2.size(); i++)
res[i + n] += a2b2[i];
return res;
}
bigint operator*(const bigint &v) const {
vector<int> a6 = convert_base(this->a, base_digits, 6);
vector<int> b6 = convert_base(v.a, base_digits, 6);
vll a(a6.begin(), a6.end());
vll b(b6.begin(), b6.end());
while (a.size() < b.size())
a.push_back(0);
while (b.size() < a.size())
b.push_back(0);
while (a.size() & (a.size() - 1))
a.push_back(0), b.push_back(0);
vll c = karatsubaMultiply(a, b);
bigint res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < (int) c.size(); i++) {
long long cur = c[i] + carry;
res.a.push_back((int) (cur % 1000000));
carry = (int) (cur / 1000000);
}
res.a = convert_base(res.a, 6, base_digits);
res.trim();
return res;
}
};
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
bigint a,b;
_for (i,0,10) {
cin >> a >> b;
cout << (a+b)/2 << '\n' << (a-b)/2 << '\n';
}
return 0;
}Bài này ở kỹ năng cá nhân. Sử dụng đệ quy để đọc vào và in ra ở dạng "Hậu thứ tự"
Tham khảo
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
char *print(char *s) {
if (*s == '(') {
s = print(s+1);
char c = *s; // the operand
s = print(s+1);
cout << c;
return s+1;
} else {
cout << *s;
return s+1;
}
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
char s[405];
cin >> n;
while (n--) {
cin >> s;
print(s);
cout << '\n';
}
}Trước tiên xét trường hợp số đó chỉ bao gồm các số 9 như 999, 999999
Lúc này số đối xứng tiếp theo sẽ có dạng 1000001. Có tổng cộng (strlen(s)-1) chữ số 0. Ta phải xét riếng trường hợp này vì nó làm tăng độ dài của số.
Chia xâu đó thành 2 phần bằng nhau. Ví dụ như 12345 sẽ thành 12 và 45, 123456 sẽ thành 123 và 456. Tức là nếu xâu có độ dài lẻ thì bỏ kí tự ở giữa.
Gọi 2 phần đó là A và B. Đảo ngược A và so sánh với B. Xét các trường hợp xảy ra như sau.
- Đảo của A nhỏ hơn hoặc bằng B. Ví dụ như số
12345,55655. Trường hợp này ta tăng phần trước B lên 1 đơn vị. rồi từ phần trc đó suy ra B mới bằng cánh lấy đối xứng qua. Kế quả thu được sẽ là12421,55755. - Đảo của A lớn hơn B. Chỉ cần lấy đối xứng là được B mới. Ví dụ
54321=>54345
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6+5;
char s[N];
int n;
void inc(char *s) {
if (*s =='9') {
*s = '0';
inc(s-1);
} else {
(*s)++;
}
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
while (n--) {
cin >> s;
int len = strlen(s);
bool only9 = true;
_for (i,0,len) {
if (s[i] != '9') {
only9 = false;
break;
}
}
if (only9) {
cout << 1;
_for (i,0,len-1) cout << 0;
cout << 1 << '\n';
continue;
}
int mid = (len-1)/2, k = mid+1;
bool bigger = true;
_for (i,k,len) {
if (s[i]<s[len-i-1]) {
bigger = false;
break;
} else if (s[i] > s[len-i-1]) break;
}
if (bigger) inc(s+mid);
while (mid>=0) {
s[len-1-mid] = s[mid];
mid--;
}
cout << s << '\n';
}
}Bài này cho m tối đa 1e9. Không thể sàng hết được theo cách thông thường. Solution: Segmented sieve hoặc Rabin Miller test
#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
vector<int> primes;
void init() {
int N = 32000;
bool *m = new bool[N];
int lim = sqrt(N);
memset(m, 1, sizeof(m[0])*N);
for (int i=2;i<lim;i++) {
if (m[i]) {
for (int j=i*i;j<N;j+=i) if (m[j]) m[j] = false;
}
}
for (int i=2;i<N;i++) if (m[i]) primes.push_back(i);
}
const int N = 1e5+5;
bool sie[N];
void print(int a,int b) {
memset(sie, 1,sizeof(sie));
for (vector<int>::iterator i = primes.begin(); i != primes.end(); ++i) {
int p = *i, k = a/p;
if (k < 2) k = 2;
for (k = k*p;k<=b;k+=p) {
if (k>=a && sie[k-a]) sie[k-a] = false;
}
}
_for (i,max(2,a),b+1) if (sie[i-a]) cout << i << '\n';
cout << '\n';
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
init();
int t,n,m;
cin >> t;
while (t--) {
cin >> m >> n;
print(m,n);
}
}#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int RAB[] = {3,5,7,11,13,17}, R = sizeof(RAB)/sizeof(RAB[0]);
LL pm(LL a, LL e, LL m) {
if (m==1) return 0;
if (!e) return 1;
LL t = 1;
while (e > 1) {
if (e&1) t = t*a%m;
a = a*a%m;
e >>= 1;
}
return t*a%m;
}
bool primeTest(LL n) {
if (n==2) return true;
if (n<2 || (n&1)==0) return false;
LL m = n-1, s = 0;
while ((m&1)==0) {
m >>= 1;
s++;
}
_for(i,0,R) {
LL k = RAB[i], b = pm(k,m,n);
if (n == k) return true;
if (n%k == 0) return false;
if (b == 1) continue;
bool pass = false;
_for (j,0,s) {
if (b == n-1) {
pass = true;
break;
}
b = b*b%n;
}
if (!pass) return false;
}
return true;
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
int T,n,m;
cin >> T;
while (T--) {
cin >> m >> n;
_for (i,m,n+1) if (primeTest(i)) cout << i << '\n';
cout << '\n';
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment