A - 你能数的清吗 51Nod

A - 你能数的清吗 51Nod - 1770(找规律)

演演是个厉害的数学家，他最近又迷上了数字谜。。。。

他很好奇 xxx...xxx(n个x)*y 的答案中有多少个z，x,y,z均为位数只有一位的整数。

大概解释一下：

22222*3 = 66666，里面有5个6。

Input 多组测试数据。第一行有一个整数T，表示测试数据的数目。(1≤T≤5000)

接下来有T行，每一行表示一组测试数据，有4个整数x，y，z，n。 (1≤x,y≤9，0≤z≤9，1≤n≤10^9) Output

对于每一组数据，输出一个整数占一行，表示答案。 Sample Input 2 2 3 6 5 3 3 0 10 Sample Output

5 0

思路

[ ] 题意：这一题给我们一个长度为n各个位数上的数均是x，然后让这个数与y相乘，得到一个多位数，问在这个多位数的位置上数等 z 等数量有多少个
[ ] 思路
- 首先这一题的数据范围是 \(1 =< n<= 1e9\),所有所用的算法复杂度\(<=O(n)\)
- 规律1：对于\(x*y<10\),这个多位数上的每一个数都相同，直接比较x*y 与 z 的值就行了
- 规律2:（在考虑这个规律之前，我们把所乘得到的多位数分开始部分、中间部分、结尾部分三个字段）对于\(x*y >=10\) ,这个时候我们就要考虑到进位的问题了，但是我们发现，虽然这个有进位问题但是其中在这个中间部分仍然可能(对于n比较的大的时候)有一个连续子段，在这子段上各个位数上的数字都相同，而对与这个多位数的 结尾部分一定只有一个数与中间部分的数不同，而在开始部分最多只包含3个数与中间连续部分呢的数一定不同，那么在这个规律的基础上解决 “进位” 所带来的麻烦情况，剩下的就是遍历去判断 z 是否与 “中间位置的那个相同的数”“开头最多超过三个数”“结尾的那个数”是否相同，因为中间部分的非常长的连续相同的字段，所以我们可以优化很多不必要的比较

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

inline void Read(int & x)

{

    int ans = 0, f = 1;

    char ch = getchar();

    while(! isdigit(ch)) { if(ch == '-') f = -1; ch =getchar(); }

    while(isdigit(ch)) { ans *= 10, ans += ch - '0'; ch = getchar(); }

    x = ans * f;

}

inline int read()

{

    char ch = getchar();

    int x = 0, f = 1;

    while(ch < '0' || ch > '9')

    {

        if(ch == '-') f = -1;

        ch = getchar();

    }

    while('0' <= ch && ch <= '9')

    {

        x = x * 10 + ch - '0';

        ch = getchar();

    }

    return x * f;

}

int main()

{

    /* freopen("A.txt","r",stdin); */

    int x, y, z, n;

    int t;

    //scanf("%d", &t);

    t = read();

    while(t --)

    {

        //scanf("%d %d %d %d", &x, &y, &z, &n);

        x = read(), y = read(), z = read(), n = read();

        if(x * y < 10)

        {

            if(x*y == z)

                printf("%d\n", n);

            else

                printf("0\n");

        }

        else

        {

            int jinzhi = x*y / 10;

            int yushu = x*y % 10;

            int a[10] = {0};

            a[yushu] ++;

            while(-- n)

            {

                yushu = (x*y + jinzhi) % 10;

                jinzhi = (x*y + jinzhi) / 10;

                if(a[yushu])

                {

                    a[yushu] += n;

                    break;

                }

                else

                {

                    a[yushu] ++;

                }

            }

            a[jinzhi] ++;

            printf("%d\n", a[z]);

        }

    }

    return 0;

}

巴特西

A - 你能数的清吗 51Nod - 1770(找规律)

思路

代码

最新文章

热门文章