51Nod 1770 數數字 c/c++題解

題目描述

輸入

多組測試資料。

第一行有一個整數T，表示測試資料的數目。(1≤T≤5000)

接下來有T行，每一行表示一組測試資料，有4個整數a，b，d，n。 (1≤a,b≤9，0≤d≤9，1≤n≤10^9)

輸出

對于每一組資料，輸出一個整數占一行，表示答案。

輸入樣例

2

3 3 9 10

3 3 0 10

輸出樣例

10

題解：

這是有點偏數學的題目，這到題目确實困擾了我很久，下面我說下我的思路(其實也很簡單)

題目的要求是aaaa…aaa * b = 積，求出積中d數字個數，這肯定是有規律可循的，因為不可能要真正的模拟乘法吧。

分為三種情況：

• a * b < 10，那麼所有的數不需要進位，如果a*b=d，那麼d的個數就是n個，如果≠就是0個，這種情況最簡單了
• a * b >= 10，那麼a*b就需要向前進位，注意這裡要考慮兩種情況：

1. (a * b)/10 + (a * b)%10 < 10，比如6666 * 2 = 13332，(6 * 2)/10 + (6 * 2)%10 = 3，也就是向前進位一次即可。

2. (a * b)/10 + (a * b)%10 >= 10，比如6666 * 8 = 53328，(6* 8)/10 + (6 * 8)%10 = 4 + 8 = 12，那這裡又需要一次進位，也就是進位兩次(不可能進位三次，因為最大也就是9+9=18，1向前進位，8落到原位，1 + 8 = 9 < 10)

   直接看代碼

代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <iterator>
using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll  INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double E = exp(1.0);
const int MOD = 1e9+7;
const int MAX = 1e5+5;
int t,a,b,d,n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> a >> b >> d >> n;
        int sum = 0;
        if(a * b < 10)
        {
            //第一種情況：每次相乘，不需要向前進位
            if(a * b == d)
            {
                sum = n;
            }
            else
            {
                sum = 0;
            }
        }
        else
        {
            //第二or第三種情況：每次相乘，需要向前進位
            if((a*b)/10 + (a*b)%10 >= 10)
            {
            	//第三種情況：進兩次位
            	/** 分為兩種情況：
					第一種：n <= 2
					n = 2，那麼最大的話a=9，也就是99，99*b，因為有進位，是以得到一個三位數，
					這個三位數是沒有啥規律的，直接while(t)看d的個數即可。
					n = 1，a*b也就是兩位數，同樣直接while(t)即可。
				 */
                if(n <= 2)
                {
                    int t = 0;
                    for(int i = 1; i <= n; i++)
                    {
                        t = t*10 + a;
                    }
                    t = t*b;
                    while(t)
                    {
                        if(t%10 == d) sum++;
                        t /= 10;
                    }
                }
                else
                {
                	/**
						當n >= 3的時候，
						比如a=6,n=3,b=8,那麼就是666*8，結果是5328，
						當n=4的時候，其他一樣，結果是53328，
						那麼就可以發現規律了，除了最左一位、最右一位，右邊數第二位，除了這幾個是沒有規律的，
						中間的n-3項都是一樣的，比如這裡的：
						5 = (6*8)/10 + 1 --- 最左一位
						8 = (6*8)%10 --- 最右一位
						2 = ((6*8)/10 + (6*8)%10)%10 = (4+8)%10 --- 右邊數第二位
						3 = ((6*8)/10 + (6*8)%10)%10 + 1 = (4+8)%10+1 --- 中間的n-3項，後面的那個+1，就是((6*8)/10 + (6*8)%10)/10 = (4+8)/10 = 1
					*/
                    int t = 0;
                    for(int i = 1; i <= 3; i++) // 隻用算出3位數然後*b，得到一個四位數即可，中間的數反正是有規律的。
                    {
                        t = t*10 + a;
                    }
                    t = t*b;
                    if(t%10 == d)// 最右一位
                        sum++;
                    if((t/10)%10 == d)// 右邊數第二位
                        sum++;
                    if((t/100)%10 == d)// 中間的n-3項
                        sum += n-2;
                    if(t/1000 == d)// 最左一位
                        sum++;
                }
            }
            else
            {
            	//第二種情況：進一次位
                if((a*b)/10 == d)
                {
                    //最前(左)一位
                    sum++;
                }
                if((a*b)/10 + (a*b)%10 == d)
                {
                    sum += n-1;
                }
                if((a*b)%10 == d)
                {
                    // 最後(右)一位
                    sum++;
                }
            }
        }
        cout << sum << endl;
    }
    return 0;
}
           

還有一種直接模拟乘法+找規律的做法，暫時還沒學。