[BZOJ1853] [스코이2010] 행운의 숫자(용척원리)

3706 단어 문제풀이성선용척 원리

제목 설명


전송문

문제풀이


BZOJ2393과 기본적으로 마찬가지로 데이터 범위가 넓습니다. b 정렬을 최대한 큰 것으로 골라서 가지를 잘라야 합니다.

코드

#include
#include
#include
#include
#include
using namespace std;
#define LL long long

LL l,r,ans;
LL a[3005],b[3005];

void get(LL x)
{
    if (x>r) return;
    a[++a[0]]=x;
    get(x*10+6);
    get(x*10+8);
}
LL gcd(LL a,LL b)
{
    if (!b) return a;
    else return gcd(b,a%b);
}
void dfs(int x,int y,LL lcm)
{
    if (x==b[0]+1)
    {
        if (y&1) ans+=r/lcm-(l-1)/lcm;
        else if (y) ans-=r/lcm-(l-1)/lcm;
        return;
    }
    dfs(x+1,y,lcm);
    LL t=gcd(lcm,b[x]);
    lcm/=t;
    if (r/lcmreturn;
    lcm*=b[x];
    dfs(x+1,y+1,lcm);
}

int main()
{
    scanf("%lld%lld",&l,&r);get(0);
    sort(a+1,a+a[0]+1);
    for (int i=1;i<=a[0];++i)
        if (a[i])
        {
            b[++b[0]]=a[i];
            for (int j=i+1;j<=a[0];++j)
                if (a[j]%a[i]==0) a[j]=0;
        }
    for (int i=1;i<=b[0]/2;++i) swap(b[i],b[b[0]-i+1]);
    dfs(1,0,1);
    printf("%lld
",ans);
}
CUIRPG를 만들어 봤습니다.
OpenShift 및 CodeReady 컨테이너에서 데이터베이스 실행

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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