• J - Just Too Lucky

  •  Gym - 100623J 
  • Since mass transit (公共交通)was invented, people who buy tickets look for lucky ticket numbers. There are many
  • notions of lucky tickets, for example sometimes tickets are considered lucky if the sum of first half of the
  • digits is equal to the sum of the second half, sometimes the product is used instead of the sum, sometimes
  • permutation of digits is allowed, etc.
  • In St Andrewburg integer numbers from 1 to n are used as ticket numbers. Bill considers a ticket lucky
  • if its number is divisible by the sum of its digits. Help Bill to find the number of lucky tickets.
  • 自从发明了公共交通,买票的人就要看幸运票号码了。有很多
  • 幸运票的概念,例如,有时门票被认为是幸运的,如果是上半年的总和
  • 数字等于下半部的和,有时使用乘积而不是求和,有时
  • 允许数字的排列等。
  • 在圣安德鲁堡,整数从1到N用作票号。比尔认为幸运票
  • 如果它的个数是由它的数字之和整除的。帮助比尔找到幸运票的数量。
  • 思路:
  • 枚举每一种各个位数的和最大为108,枚举108种情况即可。
  • #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define maxn 123
    ll dp[15][maxn][maxn][maxn];
    ll cnt,n,digit[maxn],ans;
    ll dfs(int len,int sum,int md,int cur,bool limit)
    {
        if(len==0)return sum==md&&cur==0;
        if(dp[len][sum][cur][md]!=-1&&!limit)
            return dp[len][sum][cur][md];
        int up=(limit?digit[len]:9);
        ll temp=0;
        for(int i=0; i<=up; i++)
            temp+=dfs(len-1,sum+i,md,(cur*10+i)%md,limit&&i==up);
        if(!limit)
            dp[len][sum][cur][md]=temp;
        return temp;
    }
    ll solve(ll num)
    {
        memset(dp,-1,sizeof(dp));
        while(num)
        {
            digit[++cnt]=num%10;
            num/=10;
        }
        for(int i=1; i<=108; i++)
            ans+=dfs(cnt,0,i,0,1);
        return ans;
    }
    int main()
    {
        freopen("just.in","r",stdin);
        freopen("just.out","w",stdout);
        cin>>n;
        cout<<solve(n)<<endl;
        return 0;
    }
    

     

10-06 11:39