You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

216 lines
6.0 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
// NOIP2005普及组第4题 循环
// https://www.cnblogs.com/caiyishuai/p/8585886.html
// 循环NOIP2005普及组第四题
// https://blog.csdn.net/stockholm_sun/article/details/77920783
// 未能AC
// TODO
/**
高精度模板(此高精度模板不支持负数,用的时候要小心处理)
如果传入负数,则出错
Assertion failed!
Expression: b <= *this
*/
struct BigInteger {
typedef unsigned long long LL;
static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;
BigInteger &clean() {
while (!s.back() && s.size() > 1)s.pop_back();
return *this;
}
BigInteger(LL num = 0) { *this = num; }
BigInteger(string s) { *this = s; }
BigInteger &operator=(long long num) {
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while (num > 0);
return *this;
}
BigInteger &operator=(const string &str) {
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for (int i = 0; i < len; i++) {
int end = str.length() - i * WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start, end - start).c_str(), "%d", &x);
s.push_back(x);
}
return (*this).clean();
}
BigInteger operator+(const BigInteger &b) const {
BigInteger c;
c.s.clear();
for (int i = 0, g = 0;; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
BigInteger operator-(const BigInteger &b) const {
assert(b <= *this); // 减数不能大于被减数
BigInteger c;
c.s.clear();
for (int i = 0, g = 0;; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = s[i] + g;
if (i < b.s.size()) x -= b.s[i];
if (x < 0) {
g = -1;
x += BASE;
} else g = 0;
c.s.push_back(x);
}
return c.clean();
}
BigInteger operator*(const BigInteger &b) const {
int i, j;
LL g;
vector<LL> v(s.size() + b.s.size(), 0);
BigInteger c;
c.s.clear();
for (i = 0; i < s.size(); i++) for (j = 0; j < b.s.size(); j++) v[i + j] += LL(s[i]) * b.s[j];
for (i = 0, g = 0;; i++) {
if (g == 0 && i >= v.size()) break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
BigInteger operator/(const BigInteger &b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
BigInteger m; // 余数:初始化为0
for (int i = s.size() - 1; i >= 0; i--) {
m = m * BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b * c.s[i];
}
return c.clean();
}
BigInteger operator%(const BigInteger &b) const { //方法与除法相同
BigInteger c = *this;
BigInteger m;
for (int i = s.size() - 1; i >= 0; i--) {
m = m * BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b * c.s[i];
}
return m;
}
// 二分法找出满足bx<=m的最大的x
int bsearch(const BigInteger &b, const BigInteger &m) const {
int L = 0, R = BASE - 1, x;
while (1) {
x = (L + R) >> 1;
if (b * x <= m) { if (b * (x + 1) > m) return x; else L = x; }
else R = x;
}
}
BigInteger &operator+=(const BigInteger &b) {
*this = *this + b;
return *this;
}
BigInteger &operator-=(const BigInteger &b) {
*this = *this - b;
return *this;
}
BigInteger &operator*=(const BigInteger &b) {
*this = *this * b;
return *this;
}
BigInteger &operator/=(const BigInteger &b) {
*this = *this / b;
return *this;
}
BigInteger &operator%=(const BigInteger &b) {
*this = *this % b;
return *this;
}
bool operator<(const BigInteger &b) const {
if (s.size() != b.s.size()) return s.size() < b.s.size();
for (int i = s.size() - 1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator>(const BigInteger &b) const { return b < *this; }
bool operator<=(const BigInteger &b) const { return !(b < *this); }
bool operator>=(const BigInteger &b) const { return !(*this < b); }
bool operator!=(const BigInteger &b) const { return b < *this || *this < b; }
bool operator==(const BigInteger &b) const { return !(b < *this) && !(b > *this); }
};
ostream &operator<<(ostream &out, const BigInteger &x) {
out << x.s.back();
for (int i = x.s.size() - 2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
istream &operator>>(istream &in, BigInteger &x) {
string s;
if (!(in >> s)) return in;
x = s;
return in;
}
//将高精度转为字符串
string BigIntegerToStr(BigInteger b) {
//转为字符串
ostringstream os;
os << b;
return os.str();
}
int main() {
BigInteger n, s1;
int k;
cin >> n >> k;
s1 = 1;
for (int i = 1; i <= 10; i++) {
s1 = s1 * n;
//输出字符串
string result = BigIntegerToStr(s1);
cout << result << endl;
// 倒数第k位
cout << result[result.length() - k] << endl;
//cout << "a" << endl;
}
return 0;
}