ACMの大数テンプレートの整理
ディレクトリ:.c++バージョン 1.大数演算 .大デジタル変換 .カルテル .java大数 一.c++バージョン
1.大数演算
C n=(4 n−2)C n−1 n＋1 C n=C(2 n，n)(n+1)(n=0,1,2,.)C n=C(2 n，n)−C(2 n，n−1)(n=0,1,2,.)C_n=\frac{(4 n-2)C_{n-1}{n+1}\C_n=\frac｛C（2 n，n）｝（n=0,1,2，...）\C_n=C(2 n，n)-C(2 n，n-1)(n=0,1,2，...)Cn=n+1(4 n−2)Cn−1 Cn=(n+1)C(2 n，n)(n=0,1,2，...)Cn=C(2 n，n)−C(2 n，n)−C(2 n，n=1)(n=0,2,1,2,1,…
35以内は公式で発売できます。爆発しないlong long、100以内：
1.大数演算
typedef long long ll;
const ll m=1e8;// 8
struct Bigint{
ll s[50];int l;//l
void print(){
printf("%lld",s[l]);
for(int i=l-1;i>=0;i--)printf("%08lld",s[i]);
}
void read(ll x){// x
l=-1;memset(s,0,sizeof(s));
do{
s[++l]=x%m;
x/=m;
}while(x);
}
}ans;
Bigint operator + (Bigint a,Bigint b){//
ll d=0;
a.l=max(a.l,b.l);
for(int i=0;i<=a.l;i++){
a.s[i]+=d+b.s[i];
d=a.s[i]/m;a.s[i]%=m;
}
if(d)a.s[++a.l]=d;
return a;
}
Bigint operator - (Bigint a,Bigint b){//
ll d=0;
for(int i=0;i<=a.l;i++){
a.s[i]-=d;
if(a.s[i]<b.s[i])a.s[i]+=m,d=1;
else d=0;
a.s[i]-=b.s[i];
}
while(a.l&&!a.s[a.l])a.l--;
return a;
}
Bigint operator * (int b,Bigint a){//int ( )
ll d=0;
for(int i=0;i<=a.l;i++){
d+=a.s[i]*b;a.s[i]=d%m;
d/=m;
}
while(d){
a.s[++a.l]=d%m;
d/=m;
}
return a;
}
Bigint operator / (Bigint a,int b){// int ( )
ll d=0;
for(int i=a.l;i>=0;i--){
d*=m;d+=a.s[i];
a.s[i]=d/b;d%=b;
}
while(a.l&&!a.s[a.l])a.l--;
return a;
}
Bigint operator * (Bigint a,Bigint b){//
Bigint c;memset(c.s,0,sizeof(c.s));
for(int i=0;i<=a.l;i++){
for(int j=0;j<=b.l;j++){
c.s[i+j]+=a.s[i]*b.s[j];
if(c.s[i+j]>m){
c.s[i+j+1]+=c.s[i+j]/m;
c.s[i+j]%=m;
}
}
}
c.l=a.l+b.l+10;
while(!c.s[c.l]&&c.l)c.l--;
while(c.s[c.l]>m){
c.s[c.l+1]+=c.s[c.l]/m;
c.s[c.l++]%=m;
}
return c;
}
main:
ans.read(v)、ans.read(24)、ans=ans/24(ans/=24 )、ans=23*ans(ans*=23 );
const int maxn=5000;
int t,m,n;
string str;
char hash1[maxn];
int hash2[maxn];
void init()// (36 )
{
char ch;
for(int i=0;i<36;i++){
if(i<10)ch=i+'0';
else ch='A'+i-10;
//else ch='a'+i-10;
hash1[i]=ch;
hash2[ch]=i;
}
}
string change(int m,int n,string str)// str m n
{
bool flag;
string ans="";
int temp,quo,rem;
while(true)
{
int len=str.length();
flag=false;
rem=0;
string div="";
for(int i=0;i<len;i++){
temp=rem*m+hash2[str[i]];
quo=temp/n;
rem=temp%n;
if(flag){
div+=hash1[quo];
}
else {
if(quo!=0){
flag=true;
div+=hash1[quo];
}
}
}
ans=hash1[rem]+ans;
str=div;
if(flag==false)break;
}
return ans;
}
int main()
{
init();
cin>>m>>n>>str;
string ans=change(m,n,str);
cout<<ans<<'
';
return 0;
}
C n=(4 n−2)C n−1 n＋1 C n=C(2 n，n)(n+1)(n=0,1,2,.)C n=C(2 n，n)−C(2 n，n−1)(n=0,1,2,.)C_n=\frac{(4 n-2)C_{n-1}{n+1}\C_n=\frac｛C（2 n，n）｝（n=0,1,2，...）\C_n=C(2 n，n)-C(2 n，n-1)(n=0,1,2，...)Cn=n+1(4 n−2)Cn−1 Cn=(n+1)C(2 n，n)(n=0,1,2，...)Cn=C(2 n，n)−C(2 n，n)−C(2 n，n=1)(n=0,2,1,2,1,…
35以内は公式で発売できます。爆発しないlong long、100以内：
int a[101][101];// a[i] i ,
int b[101];//b[i] i ;
void catalan() //
{
int i, j, len, carry, temp;
a[1][0] = b[1] = 1;
len = 1;
for(i = 2; i <= 100; i++)
{
for(j = 0; j < len; j++) //
a[i][j] = a[i-1][j]*(4*(i-1)+2);
carry = 0;
for(j = 0; j < len; j++) //
{
temp = a[i][j] + carry;
a[i][j] = temp % 10;
carry = temp / 10;
}
while(carry) //
{
a[i][len++] = carry % 10;
carry /= 10;
}
carry = 0;
for(j = len-1; j >= 0; j--) //
{
temp = carry*10 + a[i][j];
a[i][j] = temp/(i+1);
carry = temp%(i+1);
}
while(!a[i][len-1]) //
len --;
b[i] = len;
}
}
int main()
{
catalan();
for(int i=1;i<=100;i++){
for(int j=b[i]-1;j>=0;j--)
cout<<a[i][j];
cout<<'
';
}
return 0;
}
import java.math.*;
import java.util.*;
public class Main {
//BigDecimal
// :(1) BigInteger a = new BigInteger(string)/cin.nextBigInteger()
//(2)int t=cin.nextInt(); BigInteger a=BigInteger.valueOf(t);
public static void main(String[] args) {
Scanner cin = Scanner(System.in);
while(cin.hasNest())// !=EOF
BigInteger a=cin.nextBigInteger();
BigInteger b=cin.nextBigInteger();
int n=cin.nextInt();
//
BigInteger a.add(b);//
BigInteger a.subtract(b);//
BigInteger a.divide(b);//
BigInteger a.multiply(b);//
BigInteger a.negate()// -a
BigInteger a.remainder(b);// a%b
BigInteger a.mod(b) // (a mod b) BigInteger（ % ， ， ）
BigInteger a.modInverse(b) // ((a^(-1)) mod b) BigInteger
BigInteger a.modPow(BigInteger c,BigInteger b)// ((a^c) mod b) BigInteger(c )
boolean a.compareTo(b);// , -1, 1, 0 0
//
BigInteger a.not(); // a
BigInteger a.and(b); //a b
BigInteger a.or(b); //a b
BigInteger a.xor(b); //a b
BigInteger a.shiftLeft(n); // n n>=0
BigInteger a.shiftRight(n); // n n>=0
//
(1)String str = Integer.toString(num,base);//10 num base (x<=35)，
(2)String str.toUpperCase(); //
(3)int num=Integer.parseInt(num,base);// num base , 10 int num
(4)n=Integer.valueOf(str,x) // x 10
(1)String a.toString(n); // a n ( )
(2)String ans=new BigInteger(str,x).toString(y);//x y
//
boolean a.testBit(n); //((a & (1 << n)) != 0)
BigInteger a.setBit(n) //(a | (1 << n))
BigInteger a.clearBit(n) //(a & ~(1 << n))
BigInteger flipBit(n) //(a ^ (1 << n))
//
BigInteger a.pow(b); //a b
BigInteger a.min(b); //
BigInteger a.max(b); //
BigInteger a.gcd(b); // a b
BigInteger a.abs(); // a
int a.hashCode(); // a
boolean a.isProbablePrime(n); // a , true, , false
//（n ， true， a (1 - (1/2)^n)， ）
BigInteger a.nextProbablePrime(); // a
}
}