数学概率, 大数乘法, HDU4762

先瞎几把看样例想到一个公式, 然后yzl也说可以, 就去写了; 发现需要大整数, 但是讲道理之前并没有写过, 于是抄错了板子, 还没找到; 最后发现就是多了一个0, 去掉后交上去居然也过了; 后面再拿大整数板子写A题的时候,袁教练才来找我的板子的错误, ; 发现我k=(len-i-1)%4 写成了 k=(len-i-1)/4+1; 这才发现原来大整数的结构体都写错了, 居然给水过去了; 概率公式也被yzl强行说服了...

当然这道题的大数其实并不需要写那么多的...

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;

typedef long long ll;

int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a % b);
}

const int ten[4] = {1, 10, 100, 1000};
const int maxl = 1000;
struct BigNumber{
  int d[maxl];
  BigNumber(string s){
    int len = s.size();
    d[0] = (len-1)/4+1;
    int i, j, k;
    for(i=1;i<maxl;i++) d[i] = 0;
    for(i=len-1;i>=0;i--){
      j=(len-i-1)/4+1;
      k=(len-i-1)%4;
      d[j]+=ten[k]*(s[i]-'0');
    }
    while(d[0]>1 && d[d[0]]==0) d[0]--;
  }
  BigNumber(){
    *this = BigNumber(string("0"));
  }
  string toString(){
    string s("");
    int i, j, temp;
    for(i=3;i>=1;--i) if(d[d[0]]>=ten[i]) break;
    temp = d[d[0]];
    for(j=i;j>=0;--j){
      s=s+(char)(temp/ten[j]+'0');
      temp%=ten[j];
    }
    for(i=d[0]-1;i>0;--i){
      temp = d[i];
      for(j=3;j>=0;--j){
    s=s+(char)(temp/ten[j]+'0');
    temp%=ten[j];
      }
    }
    return s;
  }
}zero("0"), d, temp, mid1[15];

BigNumber operator *(const BigNumber &a, const int &k){
  BigNumber c;
  c.d[0] = a.d[0];
  int i, x=  0;
  for(int i=1;i<=a.d[0];i++){
    x=a.d[i]*k+x;
    c.d[i]=x%10000;
    x/=10000;
  }
  while(x>0){
    c.d[++c.d[0]] = x%10000;
    x/=10000;
  }
  while((c.d[0]>1) && (c.d[c.d[0]] == 0)) c.d[0]--;
  return c;
}

int main(){
  int t;
  int m, n, nn;
  scanf("%d", &t);
  while(t--){
    scanf("%d%d", &m, &n);
    nn = n;
    BigNumber ans = string("1");
    while(nn-- > 1){
      int dd = gcd(m, n);
      n /= dd;
      ans = ans * (m / dd);
    }
    string ss = ans.toString();
    cout<<n<<"/"<<ss<<endl;
  }
  return 0;
}