낙 곡 P1221 최대 인자 수 (검색)

2427 단어
제목 설명
수학자 들 은 다양한 종류의 이상 한 특성 을 가 진 수 를 좋아한다.예 를 들 어 그들 은 945 가 재 미 있 는 숫자 라 고 생각한다. 왜냐하면 그것 은 첫 번 째 모든 약수 의 합 이 그 자체 의 기수 보다 크기 때문이다.
그들 이 재 미 있 는 수 를 찾 도록 돕 기 위해 서 는 프로그램 을 써 서 일정한 범위 내의 수 를 스 캔 하고 이 범위 내 에서 가장 많은 수의 수 를 확정 할 것 이다.불 행 히 도 이 수 와 주어진 범위 가 넓 어 간단 한 방법 으로 찾 는 데 많은 운행 시간 이 걸 릴 수 있다.그 러 니 당신 의 알고리즘 이 몇 초 안에 최대 범위 내의 스캐닝 을 완성 할 수 있 는 지 확인 하 세 요.
입 출력 형식
입력 형식:
 
한 줄 만 있 고 스 캔 범 위 를 보 여 주 며 하계 L 과 상계 U 에서 확인 합 니 다.만족 2 ≤ L ≤ U ≤ 100000000.
 
출력 형식:
 
주어진 범위 에 대해 서 는 이 범위 내 에서 D 가 가장 많은 수의 P 를 출력 합 니 다.여러 개 있 으 면 가장 작은 것 을 출력 합 니 다."Between L and U, P has a maximum of D divisors." 를 출력 하 십시오. 그 중에서 L, U, P 와 D 의 의 미 는 앞에서 말 한 것 과 같 습 니 다.
 
입 출력 샘플
샘플 입력 \ # 1: 복제 하 다.
1000 2000

출력 샘플 \ # 1: 복제 하 다.
Between 1000 and 2000, 1680 has a maximum of 40 divisors.

PS: 사실은 인자 수가 가장 많은 수 를 찾 는 것 입 니 다. 한 수 에 따라 여러 개의 질 인자 에 의 해 분 해 될 수 있 습 니 다. 예 를 들 어 p = a1 ^ p1 + a2 ^ p2 +.131074 를 제외 하고 그 는 질 인자 가 100 보다 크 고 다른 모든 수의 인 자 는 100 보다 작 기 때문에 특 판 131074 만 있 으 면 나머지 는 dfs 질 인자 로 질 인자 수 를 뛰 면 된다.  
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
const int maxn=5e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
ll l,r,ans,sum;
ll s[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,91,97},p[30];
void check(ll s)
{
    ll res=1;
    for(int i=1;i<=26;i++)
        res*=(p[i]+1);
    if(res>sum)
        sum=res,ans=s;
    else if(res==sum)
        ans=min(s,ans);
}
void dfs(ll sum,int st)
{
    if(sum>r)
        return ;
    else if(l<=sum&&sum<=r)
        check(sum);
    for(int i=st;i<=26;i++)
    {
        p[i]++;
        dfs(sum*s[i],i);
        p[i]--;
    }
}
int main()
{
    cin>>l>>r;
    if(l==r&&l==131074)
        printf("Between 131074 and 131074, 131074 has a maximum of 4 divisors.
");
    else
    {
        dfs(1,1);
        printf("Between %lld and %lld, %lld has a maximum of %lld divisors.
",l,r,ans,sum);
    }
    return 0;
}

객체에서 값을 추출하려면 구성 해제 값 사용
문자열이 고유한지 판단

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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