回 帖 发 新 帖 刷新版面

主题:[讨论]这个题用动态规划怎么做?

我设计的状态是到第n个数为止的方案数,怎么转移啊?

Description

There are two numbers m and n, now Zero want to choose an consecutive part of m to form a new number p, so that p can be divide exactly by n. Could you write a program to calculate how many ways are there to choose p?

Input

Input will consist of multiple test cases.

For each case, there will be two numbers, m and n. 

The number of m's digits is less than 10000, and there is no '0' in m. 1 &le n &le 100

Output

Output a single number, the ways to choose p.

Sample Input

22 2
111 1
111 2
123 3
Sample Output

3
6
0
3
Hints: in case "123 3",the ways to choose are "12","3","123"

有一些数据
111 1
123 3
135 5
22 2
6985924183 2
9387868941 3
1761587696 4
3131759284 5
3734734832 9

6
3
3
3
26
17
19
6

回复列表 (共3个回复)

沙发

对于不溢出的数,下面程序可以满足了(加了个死循环方便测试)
#include <stdio.h>
#include<math.h>
main()
{
    int i,j,k,x,m,n,a[40];
    for(;;){
    scanf("%d,%d",&m,&n);
    k=0;
    for(i=0;;i++)
    {
        x=m%10;
        a[i]=x;
        m/=10;
        if(m==0)
        {
            a[i+1]=-1;
            j=i;
            break;
        }
    }
    for(i=0;i<j-i;i++)
    {
        x=a[i];
        a[i]=a[j-i];
        a[j-i]=x;
    }
    for(i=0;;i++)
    {
        if(a[i]==-1)
            break;
        for(m=0,j=i;;j++)
        {
            if(a[j]==-1)
                break;
            m*=10;
            m+=a[j];
            if(m%n==0)
                k++;
        }
    }
    printf("%d\n",k); }
}

板凳

不知道000这种算不算,下面的程序m可以是39位数(如果需要可以改大),n不能溢出最好比最大值少一两个数量级。(程序中也加了死循环)
#include <stdio.h>
#include<math.h>
main()
{
    char a[40];
    int i,j,k,m,n,x,y=1,z,frag;
    printf("输入格式:m回车n回车\n");
    for(;;){
    scanf("%s",a);
    scanf("%d",&n);
    printf("m=");
    for(i=0;;i++)
    {
        if(a[i]==0)
            break;
        printf("%c",a[i]);
    }
    printf(", n=%d\n",n);
    k=0;
    for(;;)
    {
        y*=10;
        x=y%n;
        if(y/n)
            break;
    }
    for(i=0;;i++)
    {
        if(a[i]==0)
            break;
        frag=1;
        for(m=0,j=i;;j++)
        {
            if(a[j]==0)
                break;
            m*=10;
            m+=a[j]-'0';
            //加的话不可以00这种情况
            if(m==0)
            {
                if(frag)
                    break;
            }
            else
                frag=0;
            //*****************
            if(m%n==0)
                k++;
            z=m/y;
            m%=y;
            m+=x*z;
        }
    }
    printf("%d\n\n",k); }
}

3 楼

我晕,应该不算挖坟吧?

我来回复

您尚未登录,请登录后再回复。点此登录或注册