（碰到新操作再更新…）
借鉴了neither_nor的模板，加了个快速幂，没压行
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include<bits/stdc++.h> using namespace std; struct bn{ #define MAXN 100010 #define ll long long int len; char num[MAXN]; bn(ll x){ memset(num,0,sizeof(num)); len=0; while(x>0){ num[len++]=x%10; x/=10; } } bn(){memset(num,0,sizeof(num)),len=0;} void rd(){ len=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))num[len++]=c-'0',c=getchar(); for(int i=0; i<len/2; i++)swap(num[i],num[len-i-1]); } void out(){ if(!len)printf("0"); for(int i=len-1; i>=0; i--)printf("%d",num[i]); puts(""); } void half(){ for(int i=len-1; i>0; i--){ num[i-1]+=(num[i]%2)*10; num[i]/=2; } num[0]/=2; while(len-1>=0 && !num[len-1])len--; } friend bn operator + (bn a,bn b){ bn c; for(int i=0; i<a.len || i<b.len; i++){ c.num[i]+=a.num[i]+b.num[i]; c.num[i+1]+=c.num[i]/10; c.num[i]%=10; } c.len=max(a.len,b.len); if(c.num[c.len])c.len++; return c; } friend bn operator + (bn a,ll b){return a+bn(b);} friend bn operator + (ll a,bn b){return bn(a)+b;} friend bn operator - (bn a,bn b){ bn c; for(int i=0; i<a.len; i++){ c.num[i]+=a.num[i]-b.num[i]; if(c.num[i]<0)c.num[i+1]--,c.num[i]+=10; } c.len=max(a.len,b.len); while(c.len-1>=0 && !c.num[c.len-1])c.len--; return c; } friend bn operator - (bn a,ll b){return a-bn(b);} friend bn operator * (bn a,bn b){ bn c; for(int i=0; i<a.len; i++){ for(int j=0; j<b.len; j++){ c.num[i+j]+=a.num[i]*b.num[j]; c.num[i+j+1]+=c.num[i+j]/10; c.num[i+j]%=10; } } c.len=a.len+b.len; while(c.len-1>=0 && !c.num[c.len-1])c.len--; return c; } friend bn operator * (bn a,ll b){return a*bn(b);} friend bn operator * (ll a,bn b){return bn(a)*b;} friend bool operator < (bn a,bn b){ if(a.len!=b.len)return a.len<b.len; for(int i=a.len-1; i>=0; i--)if(a.num[i]!=b.num[i])return a.num[i]<b.num[i]; return false; } friend bool operator == (bn a,bn b){ if(a.len!=b.len)return false; for(int i=0; i<a.len; i++)if(a.num[i]!=b.num[i])return false; return true; } friend bool operator <= (bn a,bn b){ return a<b || a==b; } friend bn operator / (bn a,bn b){ bn c; bn l,r,mid; l=bn(0),r=a; while(l<=r){ mid=l+r; mid.half(); if(mid*b<=a)c=mid,l=mid+1; else r=mid-1; } return c; } friend bn operator % (bn a,bn b){ return a-(b*(a/b)); } friend bn operator ^ (bn x,ll y){ bn z=1; while(y){ if(y&1)z=z*x; x=x*x; y/=2; } return z; } #undef ll #undef MAXN }; bn a,b,c; int main(){ a.rd(),b.rd(); c=a/b; c.out(); c=a-b*c; c.out(); return 0; } |