[hdu 5051]2014上海網絡賽 Fraction 數學 Benford's law/打表找規律

Fraction

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 239 Accepted Submission(s): 55


Problem Description Given a number n, and a geometric progression a_i = b * q_i, i ≥ 0, what is the fraction of the elements of that progression with decimal notation that has the decimal notation of n as prefix ?

More formally, if c_i out of the first i elements of the progression start with n in decimal notation, you need to find the limit. It is guaranteed that the limit always exists.

For example, n = 7, b = 1, q = 2. About 5.799% of all powers of two start with 7. (the smallest one is 2⁴⁶ = 70368744177664)
Input The first line of the input is T (1 ≤ T ≤ 100), which stands fZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgeW91IG5lZWQgdG8gc29sdmUuPGJyPgo8YnI+CkVhY2ggY2FzZSBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBuLGIgYW5kIHEuICgxIKHcIG4sIGIsIHEgodwgMTAwMCkKCiAKPGJyPgoKT3V0cHV0CgpGb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgbGluZSChsENhc2UgI3Q6IKGxKHdpdGhvdXQgcXVvdGVzLCB0IG1lYW5zIHRoZSBpbmRleCBvZiB0aGUgdGVzdCBjYXNlKSBhdCB0aGUgYmVnaW5uaW5nLiBUaGVuIG91dHB1dCBvbmUgZmxvYXRpbmcgbnVtYmVyIKhDIHRoZSBzb3VnaHQgZnJhY3Rpb24uIFJvdW5kIHlvdXIgYW5zd2VyIHRvIHRoZSA1dGggZGVjaW1hbCBwbGFjZS4KCiAKPGJyPgoKU2FtcGxlIElucHV0Cgo8cHJlIGNsYXNzPQ=="brush:java;">2 7 1 2 1 1 1
Sample Output

Case #1: 0.05799
Case #2: 1.00000

Source 2014 ACM/ICPC Asia Regional Shanghai Online
題目大意 給定n,b,q 設a_i = b * q^i 求當m趨近於無窮時，a1~am之中前綴為n的概率
解題思路 因為保證一定收斂，試著打表找一下規律 後來發現n取定後 不論b,q為何值都會基本收斂到一個數值，模擬100000項誤差也不是很大 最後發現關於取定的n ans=(lg(n+1)/n) 特判一下q=1,10,100,1000的情況（相當於只向後面添加0，或者保持b不變）
想到了代碼就水了，比賽的時候卡了多次邊界= =

#include 
#include 
using namespace std;
int main()
{
  int T,ca=0;
  scanf("%d",&T);   
  while (T--)
  {
    int n,b,q;
    scanf("%d%d%d",&n,&b,&q);
    double nn=n,bb=b,qq=q;/*
    以下為打表
    bb=log10(bb);

    printf("Case #%d: ",++ca);
    int ans=0;
    for (int i=1;i<=1000000;i++)
    {
      bb+=log10(q);
      if ((int) (pow(10.0,(bb-((int)(bb))))+(int)(log10(double (n)))==n)
        if (bb>bb-((int)(bb))+(int)(log10(n)))
        ans++;
    }
    printf("%.5f\n",((double)ans)/1000000);
    打表結束
    */
    double r;

    if (q==10||q==100||q==1000) 
              if (b==n||b/10==n||b/100==n||b/1000==n||b*10==n||b*100==n||b*1000==n) r=1;
              else r=0;
    else
      if (q==1) if (b==n||b/10==n||b/100==n||b/1000==n) r=1;
            else r=0;
     else r=log10((double)(n+1)/double(n)); 
    printf("%.5f\n",r);
  }
  return 0;
}