题解前先科普一下喵！序列 B 的定义基于数论中的约数和：对于每个i，B[i] = ∑ A[d]，其中d是i的所有正约数（即d能整除i）。举个栗子喵！B[4]=A[1]+A[2]+A[4]这下就能看懂了吧正式讲解代码了喵！A[1]直接赋值为输入的a1。不过这里有个小细节喵：按照题目严格来说，A[1]应
展开全文
当你发现要优化一下时间复杂度就可以暴力过be like
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define pb push_back
#define u
展开全文
倍数分配法思路(Onlogn):我们按 j 枚举 1~n，把 a[j] 加到所有 j 的倍数上：j = 1 → i=1,2,3,4,5,6 加 a[1]=10j = 2 → i=2,4,6 加 a[2]=24j = 3 → i=3,6 加 a[3]=45j =
展开全文
1. 问题分析
本题的核心要求是处理两个具有依赖关系的序列 和 。
序列 A：基于线性同余的递推关系， 仅依赖于 。这是一个单调生成的序列。
序列 B： 定义为 的所有约数 对应的 之和。这是一个经典的数论变换问题（Dirichlet Convolution 的变种，即 ，其中 是全 1
展开全文
埃氏筛法
根据题意序列 表示 是 的所有因子项的和，即
对于每一个数如果简单判断因子，其复杂度会达到 导致超时。那么我们考虑使用筛法：对于每一个下标 （），以及所有满足 的整数 ，我们将 的值累加到 上。这样，总的操作次数约为 。
由于调和级数的性质，（其中 为欧拉常数，当 时）
展开全文
思路：整体来说就是构造出A、B数组，然后把B数组的元素异或起来。对于构造A数组来说，直接根据题意模拟即可；对于构建B数组来说，首先要注意d | i表示d去整除i，而不是i去整除d，这里我开始就弄错了，然后就可以用埃式筛来构建B数组了。简单来说，埃式筛就是两层for循环，外层i的步长为1，内层j的步长
展开全文
给定，以及数组的递推式：
定义，的意思是能被整除，或者说是的一个因子。
例如，，，......
const int N = 2e6 + 10;
int n, a_begin, m;
in
展开全文
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ul
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
