[BZOJ4488][JSOI2015] 최대 공약수 DP+STL

2676 단어 dp수론STL
한 수의 약수는 대략log급이다. 그러면 오른쪽 단점이 확정한 몇몇 구간의 gcd는 가장 많이log종만 있다.분명히 오른쪽 단점이 확정되었을 때 왼쪽 단점이 점차 증가함에 따라 gcd는 떨어지지 않는다.왼쪽에서 오른쪽 DP로 현재 점을 오른쪽 단점으로 하는 구간 gcd의 수치를 기록합니다. 왼쪽 단점의 가장 왼쪽이 어디까지 뻗을 수 있는지 기록합니다.맵으로 비추면 돼.복잡도 O(nlog^2n) 코드:
#include
#include
#include
#include
#define ll long long
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
using namespace std;
typedef mapint> mpli;
int n;
ll a[100010],ans;
mpli mp,tmp;
mpli::iterator it;
ll gcd(ll a,ll b)
{
    if(aif(!b) return a;
    else return gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        chkmax(ans,a[i]);
        for(it=mp.begin();it!=mp.end();it++)
        {
            ll g=gcd(a[i],it->first);
            chkmax(ans,g*(i-it->second+1));
            if(tmp.count(g)==0) tmp[g]=it->second;
            else chkmin(tmp[g],it->second);
        }
        if(tmp.count(a[i])==0) tmp[a[i]]=i;
        mp=tmp;
        tmp.clear();
    }
    printf("%lld",ans);
    return 0;
}

Three.js 시작하기
이온 스켈레톤 로더

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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