33OJ
登录 注册

#P17780. 七海灯子不是罪过

七海灯子不是罪过

背景

『喜欢,是束缚的言语。』

题目描述

给定 nn 和三个长度为 nn 的序列 a1∼n,b1∼n,c1∼na_{1\sim n},b_{1\sim n},c_{1\sim n}。

求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_i \cdot a_j \cdot (\prod\limits_{(x\text{ is prime}) \land (x\mid \gcd(i,j))}^{}b_x)\cdot (\prod\limits_{(x\text{ is prime}) \land (x\mid \text{lcm}(i,j))}^{}c_x)$ 对 998244353998244353 取模的结果。

这里当 gcd⁡(i,j)=1\gcd(i,j)=1 时,令 $\prod\limits_{(x\text{ is prime}) \land (x\mid \gcd(i,j))}^{}b_x =1$。lcm(i,j)=1\text{lcm}(i,j)=1 同理。

输入格式

第一行两个整数 n,seedn,seed。

由于此题输入量较大,序列 a1∼n,b1∼n,c1∼na_{1\sim n},b_{1\sim n},c_{1\sim n} 均通过 seedseed 生成。具体生成示例见提示说明。

输出格式

一行一个整数表示答案。

5 0
0
2 19
510647636

提示

所以,不会喜欢别人的你,在我眼中是最温柔的人……

保证 $1\le n \le 10^6,0\le a_i,b_i,c_i \le 10^9,0\le seed < 10^{18}$。

输入示例:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1e6 + 10;
int n, a[N], b[N], c[N];
ull seed;
ull Rnd(){
	seed ^= seed << 5;
	seed ^= seed >> 11;
	seed ^= seed << 54;
	return seed;
}
int main(){
	cin >> n >> seed;
	for(int i = 1; i <= n; ++ i) a[i] = Rnd() % 1000000001;
	for(int i = 1; i <= n; ++ i) b[i] = Rnd() % 1000000001;
	for(int i = 1; i <= n; ++ i) c[i] = Rnd() % 1000000001;
	cout << "666";
	return 0;
}