2017-ACM-ICPC-Asia-Shenyang

A. BBP Formula

题意

$$\pi=\sum_{k=0}^{\infty}\frac 1 {16^k}\left( \frac 4 {8k+1}-\frac 2 {8k+4}-\frac 1 {8k+5}-\frac 1 {8k+6}\right)$$

求 $\pi$ 十六进制表达的小数点后第 $n$ 位.

题解

求十进制小数的十六进制形式, 去掉整数部分, 小数部分乘 16 得到的数的整数部分就是小数点后第一位的十六进制值, 以此类推.

$$16^n\sum_{k=0}^{\infty}\frac 1 {16^k} \frac 4 {8k+1} =\sum_{k=0}^{n}\frac {4*16^{n-k}\%(8k+1)} {8k+1}+\sum_{k=n+1}^{\infty}\frac 4 {16^{k-n}(8k+1)}$$

代码

int n;
ll qPow(ll a, ll b, ll c) {  //求(a^b) % c
    ll ret = 1;
    while (b) {
        if (b & 0x1) ret = ret * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ret;
}
db fun(int a,int b){
    db ans=0;
    for0(i,n+1){
        ll w=a*qPow(16,n-i,8*i+b)%(8*i+b);
        ans+=(db)w/(8*i+b);
    }
    ll ppow=1;
    for1(i,15){
        ppow*=16;
        // cout<<ppow<<endl;
        ans+=(db)a/ppow/(8*(i+n)+b);
    }
    return ans;
}
int main() {
    int t;
    in(t);
    for1(ca,t){
        in(n);
        n--;
        db ans=fun(4,1)-fun(2,4)-fun(1,5)-fun(1,6);
        // cout<<ans<<endl;
        while(ans<0)ans++;
        while(ans>1)ans--;
        // cout<<ans<<endl;
        int k=ans*16;
        // cout<<k<<endl;
        if(k>=10)printf("Case #%d: %d %c\n",ca,n+1,k-10+'A');
        else printf("Case #%d: %d %d\n",ca,n+1,k);
    }
    return 0;
}

F. Heron and His Triangle

题意

设三角形的三条边为 $t-1,t,t+1$ ，给一个 $n(1\le n\le 1e30)$ ，求大于 $n$ 且三角形面积为整数的最小 $t$

题解

由海伦公式得

$$S=\sqrt {p(p-a)(p-b)(p-c)}\ ,p=\frac {a+b+c}2\\ S=\frac t 2\sqrt {3\left(\left(\frac t 2\right)^2-1\right)}\\ assume\qquad x=\frac t 2\\ x^2-3y^2=1\\ x_n=4x_{n-1}-x_{n-2}$$

代码

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Main{
   public static void main(String[] args) throws IOException{
	   Scanner sc =new Scanner(System.in);
	   int t;
	   t = sc.nextInt();
	   BigInteger n,maxn=new BigInteger("1000000000000000000000000000000");
	   Vector<BigInteger>v = new Vector<>();
	   v.add(BigInteger.valueOf(4));
	   v.add(BigInteger.valueOf(14));
	   while(v.lastElement().compareTo(maxn)==-1) {
		   int qq = v.size();
		   v.add(v.elementAt(qq-1).multiply(BigInteger.valueOf(4)).subtract(v.elementAt(qq-2)));
     }
	   while(t--!=0) {
		   n=sc.nextBigInteger();
		   for(Iterator<BigInteger> iter = v.iterator();iter.hasNext();) {
			   BigInteger tmp=iter.next();
			   if(tmp.compareTo(n)>=0) {
				   System.out.println(tmp);
				   break;
			   }
		   }
	   }
	   sc.close();
   }
}