题解 P2429 【制杖题】

· · 题解

upd：2020.09.06

貌似是个送分zz题。/fad

虽然是道绿题，但由于是个zz题，所以难度没有那么高。

思路解析

读入一个 P_i，因为保证 P_i 为质数，所以 j\cdot P_i(j\in\mathbb{N} 并且 j > 0) 分解质因数后必存在质因子 P_i。

每次读一个，就进行在线处理：枚举倍数 j，找到所有的 j\cdot P_i\le m，把它们加起来。（别忘记取模，模数：376544743

值得注意的是，可能存在 a\cdot P_i=b\cdot P_j 的情况，所以必须开一个Hash进行记录，重复的不再加入答案中。因为我学的c++，所以使用红黑树 map 当Hash用，代码中的 unordered_map 是不排序的（unordered）红黑树，效率比 map 要高。因为我们只把其当Hash使用，所以不需要排序。

另外记得要开 long long，否则就要见祖宗。

CODE

#include <stdio.h>
#include <unordered_map>
int n, m;
std:: unordered_map<long long, bool> vis; //不排序的红黑树
int main(void) {
    scanf("%d %d", &n, &m);
    long long ans = 0, pri, now;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &pri); //在线读入，不开数组
        for (int j = 1; pri * j <= m; ++j) { //枚举倍数
            now = pri * j;
            if (!vis[now]) { //now没有重复计算
                vis[now] = true; //标记为已找到now
                ans += now; //累计答案
                ans %= 376544743ll; //别忘记取模
            }
        }
    }
    printf("%lld\n", ans); //结束
    return 0;
}

喜欢就留个赞嘛qwq