poj-2514-模拟

Ridiculous Addition

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1954		Accepted: 412

Description

Let us write down the infinite consecutive integers in a sequence in one line without any space and their squares in the second line. This will generate two different long numbers, now we want to find the sum of these two numbers. The calculation of the first 30 digits is just as below.

The first digit of the result is 2, the second digit is 7, and the third is 2 and so on. Given an integer k, you should output the digit at position k in the resulting number.

Input

The input file will contain several test cases. In each of the test cases, there is an integer k (0 < k <= 2 ^ 31 - 1) in one line.

A line containing a number "0" terminates input, and this line need not be processed.

Output

For each test case you should generate a line of output, which is the digit in the k-th place of the addition result.

Sample Input

Sample Output

7
1
8

Source

POJ Monthly--2005.07.31, Islamic Azad University of Mashhad – Collegiate Coding Challenge 1

　　　　给出两个无限长的数 A=123456789101112131415...... 和B=149162536496481100121144...... 求A+B的第K位数是多少。

　　　由于是加法运算所以进位最多就是1，只要计算出A的第k位和B的第k位就差不多解决了，问题转化为求解A和B的第k位是多少。

　　　　按照数位dp那种思想按位数分一下类就好了，对于同一位数的数做出的贡献很好计算，就是 len(num)*sum , A就分成[0,9,99,999,9999......],B的话就是[0,sqrt(10)-eps,sqrt(100)-eps,sqrt(1000)-eps......]

设置eps的必要性在于对于10000=100*100来说，我想得到的是99而不是100，所以减去一个eps来得到，就是因为这里计算错误导致一直WA= =

　　　　做出位数贡献的前缀和然后xjb二分下就好了。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<cmath>
  6 using namespace std;
  7 #define LL long long
  8 vector<LL>g[2];
  9 LL a[20],b[20];
 10 LL max_int=2147483647;
 11 void init()
 12 {
 13     g[0].push_back(0);
 14     g[1].push_back(0);
 15     LL x=9,y=10;
 16     for(int i=1; i<=18; ++i,x=x*10+9,y*=10)
 17     {
 18         g[0].push_back(x);
 19         g[1].push_back((LL)(sqrt(y)-0.00001));
 20     }
 21     LL o=10;
 22     for(int i=1; i<=10; ++i,o*=10)
 23     {
 24         a[i]=a[i-1]+i*(o-o/10);
 25     }
 26     for(LL i=1; i<=18; ++i)
 27     {
 28         b[i]=b[i-1]+i*(g[1][i]-g[1][i-1]);
 29     }
 30 }
 31 int getl(LL n)
 32 {
 33     int ans=0;
 34     while(n) ans++,n/=10;
 35     return ans;
 36 }
 37 int get_a(LL n)
 38 {
 39     LL l=1,r=999999999;
 40     while(l<r)
 41     {
 42         LL mid=l+(r-l)/2;
 43         LL len=getl(mid);
 44         LL s=a[len-1]+(len*(mid-g[0][len-1]));
 45         if(s>n)
 46         {
 47             r=mid;
 48         }
 49         else if(s<n)
 50         {
 51             l=mid+1;
 52         }
 53         else
 54         {
 55             return mid%10;
 56         }
 57     }
 58     LL len=getl(l);
 59     LL s=a[len-1]+(len*(l-g[0][len-1]));
 60     while(s>n) s--,l/=10;
 61     return l%10;
 62 }
 63 
 64 
 65 int get_b(LL n)
 66 {
 67     LL l=1,r=317227766;
 68     while(l<r)
 69     {
 70         LL mid=l+(r-l)/2;
 71         LL len=getl(mid*mid);
 72         LL s=b[len-1]+(len*(mid-g[1][len-1]));
 73         if(s>n)
 74         {
 75             r=mid;
 76         }
 77         else if(s<n)
 78         {
 79             l=mid+1;
 80         }
 81         else
 82         {
 83             return mid*mid%10;
 84         }
 85     }
 86     LL len=getl(l*l);
 87     LL s=b[len-1]+(len*(l-g[1][len-1]));
 88     l=l*l;
 89     while(s>n) s--,l/=10;
 90     return l%10;
 91 }
 92 
 93 int main()
 94 {
 95     LL n;
 96     init();
 97     while(scanf("%lld",&n)!=EOF)
 98     {
 99         if(!n) break;
100         LL a=get_a(n),b=get_b(n),
101            c=get_a(n+1),d=get_b(n+1),jin=0;
102         while(c+d>8)
103         {
104             if(c+d>9)
105             {
106                 jin=1;
107                 break;
108             }
109             n++;
110             c=get_a(n+1);
111             d=get_b(n+1);
112         }
113         cout<<(a+b+jin)%10<<endl;
114     }
115     return 0;
116 }