디지털 dp CF 55 D.아름 다운 숫자

2720 단어 동적 계획
제목 링크:
http://codeforces.com/problemset/problem/55/D
 
제목 의 대의:
구간 내 에서 각 비트 의 0 이 아 닌 정수 에 만족 할 수 있 는 개 수 를 구하 다.데이터 범위:9*10^18
 
문제 풀이 방향:
lcm(1,2,3,4,5,6,7,8,9)=2^3*3^2*5*7=2520  공약수 의 총 개 수 는 4*3*2*2=48 개 이다
a%b=0 a%(k*b)%b=0 출시 가능
그러므로 기억 화 된 검색 dfs(cur,mod,llcm,flag)를 사용 할 수 있 습 니 다.개 비트 에서 cur 비트 까지,이전의%2520 은 mod 이 고,이전의 여러분 의 최소 공 배 수 는 llcm,flag=1 이 며,이전의 모든 것 이 최고 위 였 음 을 나타 낸다.flag=0 은 이전의 것 이 모두 최고 위 가 아니 었 음 을 나타 낸다(즉 일반적인 상황)
2 분 으로 이 최소 공배수 의 위 치 를 찾 습 니 다(이산 화 처리 2520 내 가능 한 약수)
 
코드:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;
#define ll __int64
#define MOD  2520  //lcm(1,2,3,4,5,6,7,8,9)=2^3*3^2*5*7          4*3*2*2=48 

ll save[50];
ll dp[20][2530][50];
ll pos[20];
int cnt;

ll gcd(ll a,ll b)
{
    if(a%b==0)
        return b;
    return gcd(b,a%b);

}

ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

void init()
{
    cnt=0;
    for(int i=1;i<=MOD;i++)   //  （1-9）        
        if(MOD%i==0)
            save[cnt++]=i;
    cnt--;
    memset(dp,-1,sizeof(dp));  //          
    return ;
}

ll bs(ll a)
{
    int le=0,ri=cnt,mid;

    while(le<=ri)   //            
    {
        mid=(le+ri)>>1;

        if(a==save[mid])
            return mid;  //      

        if(a>save[mid])
           le=mid+1;
        else
            ri=mid-1;
    }

}
ll dfs(ll cur,ll mod,ll llcm,ll flag)
{
    if(cur==-1)
        return (mod%save[llcm])?0:1;  //          

    if(!flag&&dp[cur][mod][llcm]!=-1)
        return dp[cur][mod][llcm];  //     ，             ，

    int Max=flag?pos[cur]:9; //         pos[cur]，         9

    ll res=0;

    for(int i=0;i<=Max;i++)
    {
        ll temp=(mod*10+i)%MOD;
        ll lccm=llcm;

        if(i)
            lccm=bs(lcm(i,save[llcm]));  //             

        res+=dfs(cur-1,temp,lccm,flag&&(i==Max));
    }
    if(!flag)
        dp[cur][mod][llcm]=res;

    return res;
}

ll Cal(ll a)
{
    int num=0;

    while(a)  //     
    {
        pos[num++]=a%10;
        a/=10;
    }
    return dfs(num-1,0,0,1);
}

int main()
{
    init();
    int t;
    ll a,b;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&a,&b);
        printf("%I64d
",Cal(b)-Cal(a-1));
    }

   return 0;
}

HTML 5 video 태그 재생 제어
Wormholes

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage