CF D. Beautiful numbers （數(shù)位dp）
來源：程序員人生 發(fā)布時(shí)間：2014-09-06 19:09:08 閱讀次數(shù)：3530次
http://codeforces.com/problemset/problem/55/D
Beautiful Numbers : 這個(gè)數(shù)能整除它的所有位上非零整數(shù)。問[l,r]之間的Beautiful Numbers的個(gè)數(shù)。
若一個(gè)數(shù)能整除它的所有的非零數(shù)位，那么相當(dāng)于它能整除個(gè)位數(shù)的最小公倍數(shù)。因此記憶化搜索中的參數(shù)除了len(當(dāng)前位)和up（是否達(dá)到上界），有一個(gè)prelcm表示前面的數(shù)的最小公倍數(shù)，判斷這個(gè)數(shù)是否是Beautiful Numbers，還要有一個(gè)參數(shù)表示前面數(shù)，但是這個(gè)數(shù)太大，需要縮小它的范圍。
難點(diǎn)：
縮小前面組成的數(shù)的范圍。
可以發(fā)現(xiàn)所有個(gè)位數(shù)的最小公倍數(shù)是2520，假設(shè)當(dāng)前的Beautiful Numbers是x，
那么 x % lcm{dig[i]} = 0,
又 2520%lcm{dig[i]} = 0，
那么x%2520%lcm{ dig[i] } = 0，x范圍由9*10^18變?yōu)?520。
處理超內(nèi)存問題。
經(jīng)過分析后可以設(shè)出dp[20][2050][2050]，dp[i][j][k]表示處理到i位，前面的數(shù)的最小公倍數(shù)為j，前面的數(shù)%2520為k。但這樣
明顯會(huì)TLE。。因?yàn)?~9組成的最小公倍數(shù)只有48個(gè)，可以離散化，這樣數(shù)組就降到了dp[20][50][2520]。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;
const int max_lcm = 2520;
LL gcd(LL a, LL b)
{
if(b == 0)
return a;
return gcd(b,a%b);
}
LL lcm(LL a, LL b)
{
return a/gcd(a,b)*b;
}
int dig[25];
LL dp[25][50][2525];
int hash[2525];
LL dfs(int len, int prelcm, int prenum, int up)
{
if(len == 0)
{
return prenum%prelcm == 0;
}
if(!up && dp[len][hash[prelcm]][prenum] != -1)
return dp[len][hash[prelcm]][prenum];
int n = up ? dig[len] : 9;
LL res = 0;
for(int i = 0; i <= n; i++)
{
int nownum = (prenum*10+i)%max_lcm;
int nowlcm = prelcm;
if(i)
nowlcm = lcm(prelcm,i);
res += dfs(len-1,nowlcm,nownum,up&&i==n);
}
if(!up)
dp[len][hash[prelcm]][prenum] = res;
return res;
}
LL cal(LL num)
{
int len = 0;
while(num)
{
dig[++len] = num%10;
num /= 10;
}
return dfs(len,1,0,1);
}
int main()
{
int test;
LL a,b;
int cnt = 0;
for(int i = 1; i <= 2520; i++) //離散化
{
if(max_lcm % i == 0)
hash[i] = ++cnt;
}
scanf("%d",&test);
memset(dp,-1,sizeof(dp));
for(int item = 1; item <= test; item++)
{
scanf("%I64d %I64d",&a,&b);
printf("%I64d
",cal(b) - cal(a-1));
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
