题解 P2429 【制杖题】

田大坑 · 2018-10-23 20:36:32 · 题解

又是一道制杖题

对于一堆素数，可以使用（普及—）模板，把所给的素数乘上它的倍数，就可以完美解决了，筛法的时间复杂度是O（NloglogN），基本上是O（N）了

可是由于重复状态的重复计数和MLE，使得我们从 100pts ————> 70pts

很明显，如何去重以及压缩空间是一个问题

HASH

本人和楼下的 @白烛葵 是一个机房的，对于判重，hash是要优于map的吧……？

对于一个数字，%上一个较大的指数，就是hash，代码很简单

如果有一个数占用这个位置，就+1，接着找就可以了，这一步叫处理冲突

对于%数，要合理选择，在空间和时间选择一个有利的点

那么有了这些知识储备，就可以水过这到题目了

时间120ms+，空间80MB+ qwq

#include<bits/stdc++.h>
#define int long long
#define mod 376544743
#define p 10000007//%数越大，冲突越少，最好%上一个素数
#define hash(a) a%p
using namespace std;
int a[201],n,m;
int ans,h[p];
int find(int x)//处理冲突
{
    int y=hash(x);
    while(h[y]&&h[y]!=x)
    y=hash(++y);
    return y;
}
void push(int x)//加入hash表
{h[find(x)]=x;}
bool check(int x)//看有没有出现过
{return h[find(x)]==x;}
signed main()
{
//  freopen("in.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i*a[1]<=m;i++)
    {
        for(int j=1;j<=n&&i*a[j]<=m;j++)//筛法处理素数
        {
            if(!check(a[j]*i))//判重
            {
                push(a[j]*i);//丢入表中
                ans+=a[j]*i;
                ans%=mod;
            }
        }
    }
    printf("%lld",ans%mod);
}

stl大法好 30ms+ 2MB-

#include<bits/stdc++.h>
#define int long long
#define mod 376544743
using namespace std;
int a[201],n,m;
int ans;
map<int,bool> mp;
signed main()
{
//  freopen("in.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i*a[1]<=m;i++)
    {
        for(int j=1;j<=n&&i*a[j]<=m;j++)
        {
            if(mp.find(a[j]*i)==mp.end())
            {
                mp[a[j]*i]=1;
                ans+=a[j]*i;
                ans%=mod;
            }
        }
    }
    printf("%lld",ans%mod);
}