#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
struct bigint{
int v[35]={0};
};
int mod = 1e9;
bigint add(bigint a, bigint b){
bigint c;
for(int i=0;i<=30;i++){
c.v[i] += a.v[i]+b.v[i];
if(c.v[i]>mod){
c.v[i] -= mod;
c.v[i+1]++;
}
}
return c;
}
bigint sub(bigint a, bigint b){
bigint c;
for(int i=0;i<=30;i++){
c.v[i] = a.v[i]-b.v[i];
if(c.v[i]<0){
c.v[i] += mod;
a.v[i+1]--;
}
}
return c;
}
bigint mult(bigint a, bigint b){
bigint c;
for(int i=0;i<=30;i++){
for(int j=0;j<=30;j++){
if(i+j<=30){
c.v[i+j] += a.v[i]*b.v[j];
c.v[i+j+1] += c.v[i+j]/mod;
c.v[i+j] %= mod;
}
}
}
return c;
}
bool bigeq(bigint a, bigint b){
for(int i=30;i>=0;i--){
if(a.v[i]>b.v[i]){
return true;
}
else if(a.v[i]<b.v[i]){
return false;
}
}
return true;
}
string s;
bigint n,one,two;
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
one.v[0] = 1;
two.v[0] = 2;
cin >> s;
reverse(s.begin(),s.end());
for(int i=s.length()-1;i>=0;i--){
n.v[i/9] *= 10LL;
n.v[i/9] += s[i]-'0';
}
n = mult(n,two);
bigint tosub;
for(int j=14;j>=0;j--){
int low=0,high=mod-1;
while(low!=high){
int mid = (low+high+1LL)/2LL;
tosub.v[j] = mid;
if(bigeq(mult(tosub,add(tosub,one)),n)){
high = mid-1LL;
}
else{
low = mid;
}
}
tosub.v[j] = low;
}
tosub = add(tosub,one);
n = sub(n,tosub);
bool ld=false;
for(int i=30;i>=0;i--){
if(ld){
string p = to_string(n.v[i]);
while(p.length()!=9){
p = "0"+p;
}
cout << p;
}
if(n.v[i]>0){
cout << n.v[i];
ld = true;
}
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
