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;
}
           

还有一种直接模拟乘法+找规律的做法，暂时还没学。