题解 P2429 【制杖题】

· · 题解

emmmmmm
为什么要用线筛？？？？？？
不感觉很麻烦吗？？？？？？
既然是智障制杖题，那么肯定要用很简单的算法啦~
下面，我就提供一种非常便于理解的膜你算法~~~
很明显，做了这题的人都会想到去重这个东西，bool数组是不现实的，那么鉴于n的值很小，我们就想到了暴力模拟，下面贴出代码（头文件啥的就不发了）：

int n,m,ans;
int a[25];//定义
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){//边读边做
        scanf("%d",&a[i]);//读入
        for(int j=a[i];j<=m;j+=a[i]){//题目说明了集合里一定是质数，所以只需要考虑集合里质数的倍数就好了
            bool ok=true;//bool变量
            for(int k=1;k<i;k++){//因为n很小，并且基于一点贪心的思想，就可以用一个模拟去重
                if(j%a[k]==0){
                    ok=false;//如果取过了，就不取
                }
            }
            if(ok){//没有取过的情况
                ans+=j;
                ans%=376544743;//取模
            }
        }
    }
    printf("%d\n",ans);//输出
    return 0;
}

是不是很好理解呢~~~
本人QQ：2124652975，对题目有不理解的地方或是觉得在下表述不清的dalao欢迎骚扰~
最后祝NOIP2018 RP+++++++++~