qduoj 153 cfenglv的一道简单签到题 （二分+分解因子）

cfenglv的一道简单签到题

发布时间: 2017年6月11日 17:59   最后更新: 2017年6月11日 18:11   时间限制: 4000ms   内存限制: 128M

描述

据说，julyc决定给学弟学妹出一场月赛，于是他脑中浮现了许多很棒棒的出题创意。

而cfenglv恰巧在机房，于是他把一道题的创意说给了cfenglv听：

求区间gcd（最大公约数）大于等于k的最大区间长度len

这个问题cfenglv思考了一下，发现可以做，但是又不想做，于是提议放到月赛上给其他人做，julyc表示同意。

那么，你能把这个这么棒棒的问题给解决吗？

输入

第一行一个整数t代表数据组数
接下来每组数据
第一行输入两个整数n,k
0<n,k<=1e5
接下来n个正整数
保证所有数据不大于1e5

输出

每组数据输出一行，并输出ans

样例输入1 复制

1
5 3
3 6 9 2 5 

样例输出1

3

思路： 二分长度， 把每个数所有因子都提出来，如果某一段区间有超过这段区间长度个因子，并且这个因子》=k就好了， 因子最多sqrt*2， 那么总的复杂度就是 sqrt*2*n*log 1e7左右。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> fac[maxn];
int a[maxn], cnt[maxn], t, n, k;
int check(int x)  //这里比较巧妙， 先从头找长度x个，然后不断向左移动， 移动时候 就先把第一个的因子删掉，加上新的这个因子就好了。。两个for
{
    for(int i = 1; i <= x; i++)
    {
        for(int j = 0; j < fac[i].size(); j++)
        {
            cnt[fac[i][j]]++;
            if(cnt[fac[i][j]] >= x && fac[i][j] >= k) return 1;
        }
    }
    for(int i = x+1; i <= n; i++)
    {
        int tem = i-x;
        for(int j = 0; j < fac[tem].size(); j++)
            cnt[fac[tem][j]]--;
        for(int j = 0; j < fac[i].size(); j++)
        {
            cnt[fac[i][j]]++;
            if(cnt[fac[i][j]] >= x && fac[i][j] >= k) return 1;
        }
    }
    return 0;
}
int main()
{
    cin >> t;
    while(t--)
    {
        for(int i = 1; i <= n; i++)
            fac[i].clear();
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= sqrt(a[i]); j++)
            {
                if(a[i]%j) continue;
                fac[i].push_back(j);
                if(a[i]/j != j)
                    fac[i].push_back(a[i]/j);
            }
        }
        int l = 1, r = n, mid, ans = 0;
        while(l <= r)
        {
            mid = (l+r)/2;
            if(check(mid)) ans = mid, l = mid + 1;
            r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

一共 就1e5 ，可以把1-1e5所有的的数的因子都找出来， 那样就不用每次都打表了 标程代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
vector<int>g[maxn];
int num[maxn],a[maxn];
void get_div(int n) 
{
	for(int i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			if(n/i!=i)
			g[n].push_back(n/i);
			g[n].push_back(i);
		}
	}
}
void init()  //把所有的数的因子都弄出来
{
	for(int i=1;i<=1e5;i++)
		get_div(i);
}
int check(int len,int k,int n)
{
	memset(num,0,sizeof(num));
	for(int i=1;i<=len;i++)
	{
		for(int j=0;j<g[a[i]].size();j++)
		{
			if(g[a[i]][j]<k)
			continue;
			num[g[a[i]][j]]++;
			if(num[g[a[i]][j]]==len)
			return 1;
		}
	}
	for(int i=len+1;i<=n;i++)
	{
		for(int j=0;j<g[a[i-len]].size();j++)
		{
			if(g[a[i-len]][j]<k)
			continue;
			num[g[a[i-len]][j]]--;
		}
		for(int j=0;j<g[a[i]].size();j++)
		{
			if(g[a[i]][j]<k)
			continue;
			num[g[a[i]][j]]++;
			if(num[g[a[i]][j]]==len)
			return 1;
		}
	}
	return 0;
}
int main()
{
	int t;
	init();
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		int l=0,r=n+1;
		while(r-l>1)
		{
			int mid=(l+r)/2;
			if(check(mid,k,n))
			l=mid;
			else
			r=mid;
		}
	//	printf("test %d\n",a[100000-50]);
		printf("%d\n",l);
	}
	return 0;
}