#include <bits/stdc++.h>
using namespace std;
#define io \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
ll bp(ll n,ll m){
if(m == 0){
return 1;
}
if(m == 1){
return n;
}
if(m%2==0){
return bp(n*n,m/2);
}
return n*bp(n,m-1);
}
const int N = 1e6 + 545, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;
string sum(string a,string b) {
string res;
if((int)a.size() < (int)b.size()) {
swap(a,b);
}
reverse(a.begin() , a.end());
reverse(b.begin() , b.end());
int tmp = 0;
for(int i=0;i<(int)a.size();i++) {
if((int)b.size() <= i) {
res = res + char(((a[i] - '0') + tmp)%10 + '0');
tmp = ((a[i] - '0') + tmp)/10;
}
else {
res = res + char(((a[i] - '0') + tmp + (b[i] - '0')%10) + '0');
tmp = ((a[i] - '0') + tmp + (b[i] - '0'))/10;
}
}
if(tmp > 0) {
res = res + char(tmp);
}
reverse(res.begin() , res.end());
return res;
}
string div(string a) {
string res;
//reverse(a.begin() , a.end());
int tmp = 0;
for(int i=0;i<(int)a.size();i++) {
if((tmp * 10 + (a[i] - '0'))/2 == 0) {
tmp = (a[i] - '0');
if(res.size() == 0) {
continue;
}
res = res + '0';
}
else {
int eded = (tmp * 10 + (a[i] - '0'))%2;
string tt = to_string(((tmp * 10 + (a[i] - '0'))/2));
res = res + tt;
tmp = eded;
}
}
return res;
}
string mul(string a, string b) {
int m = a.size() , n = b.size();
string res(m + n, '0');
for(int i=m-1;i>=0;i--) {
int tmp = 0;
for(int j=n-1;j>=0;j--) {
int cur = (a[i] - '0') * (b[j] - '0') + (res[i + j + 1] - '0') + tmp;
res[i + j + 1] = cur % 10 + '0';
tmp = cur / 10;
}
res[i] += tmp;
}
// Remove leading zeros
size_t it = res.find_first_not_of('0');
if (it != std::string::npos) {
return res.substr(it);
}
return "0";
}
string sub(string a, string b) {
int m = a.size() , n = b.size();
string res(max(m, n), '0');
int tmp = 0;
for(int i=0;i<max(m, n);i++) {
int fi = (i < m) ? (a[m - 1 - i] - '0') : 0 , se = (i < n) ? (b[n - 1 - i] - '0') : 0;
int cur = fi - se - tmp;
if(cur < 0) {
cur += 10;
tmp = 1;
}
else {
tmp = 0;
}
res[res.size() - 1 - i] = cur + '0';
}
// Remove leading zeros
size_t it = res.find_first_not_of('0');
if (it != std::string::npos) {
return res.substr(it);
}
return "0";
}
int main() {
string n;
cin >> n;
string l = "1" , r = n , res = "-1";
while(l <= r) {
string mid = div(sum(l , r));
if(div(mul(mid , sum(mid , "1"))) >= n) {
r = sub(mid , "1");
res = mid;
}
else {
l = sum(mid , "1");
}
}
cout << sub(mul("2" , n) , res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
