103175: [Atcoder]ABC317 F - Nim
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：3
Solved：0
Description
Score : $500$ points
Problem Statement
You are given integers $N,A_1,A_2,A_3$. Find the number, modulo $998244353$, of triples of positive integers $(X_1,X_2,X_3)$ that satisfy all of the following three conditions.
- $1\leq X_i \leq N$ for every $i$.
- $X_i$ is a multiple of $A_i$ for every $i$.
- $(X_1 \oplus X_2) \oplus X_3 = 0$, where $\oplus$ denotes bitwise xor.
What is bitwise xor?
The bitwise xor of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.- When $A \oplus B$ is written in binary, the $2^k$s place ($k \geq 0$) is $1$ if exactly one of the $2^k$s places of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 10^{18}$
- $1 \leq A_i \leq 10$
- All input values are integers.
Input
The Input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $A_3$
Output
Print the answer.
Sample Input 1
13 2 3 5
Sample Output 1
4
Four triples $(X_1,X_2,X_3)$ satisfy the conditions: $(6,3,5),(6,12,10),(12,6,10),(12,9,5)$.
Sample Input 2
1000000000000000000 1 1 1
Sample Output 2
426724011
Sample Input 3
31415926535897932 3 8 4
Sample Output 3
759934997
Input
Output
得分：500分
问题描述
给你一些整数 $N,A_1,A_2,A_3$。找出满足以下三个条件的正整数三元组 $(X_1,X_2,X_3)$ 的数量，对 $998244353$ 取模。
- 对于每一个 $i$，都有 $1\leq X_i \leq N$。
- 对于每一个 $i$，都有 $X_i$ 是 $A_i$ 的倍数。
- $(X_1 \oplus X_2) \oplus X_3 = 0$，其中 $\oplus$ 表示按位异或。
什么是按位异或？
非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下：- 当 $A \oplus B$ 用二进制表示时，第 $2^k$ 位（$k \geq 0$）为 $1$，当 $A$ 和 $B$ 的第 $2^k$ 位中恰有一个为 $1$，否则为 $0$。
约束条件
- $1 \leq N \leq 10^{18}$
- $1 \leq A_i \leq 10$
- 所有输入值都是整数。
输入
标准输入给出以下格式的输入：
$N$ $A_1$ $A_2$ $A_3$
输出
输出答案。
样例输入 1
13 2 3 5
样例输出 1
4
有四个三元组 $(X_1,X_2,X_3)$ 满足条件：$(6,3,5),(6,12,10),(12,6,10),(12,9,5)$。
样例输入 2
1000000000000000000 1 1 1
样例输出 2
426724011
样例输入 3
31415926535897932 3 8 4
样例输出 3
759934997