首页 > 试题广场 >

华华给月月出题

[编程题]华华给月月出题
  • 热度指数：2 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题：

符号表示异或和，详见样例解释。
虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。

输入描述:
输入一个正整数N。


输出描述:
输出答案Ans。
示例1

输入

3

输出

18

说明

N=3时，1^3=1，2^3=8，3^3=27，异或和为18。
示例2

输入

2005117

输出

863466972

备注:
算法知识视频讲解
开通博客
头像 lzlwdz
发表于 2024-05-01 10:16:02
题解说的好玄乎,其实就是分配律 该题数据范围过大,直接快速幂会超时,所以我们预处理质数的快速幂,利用线性筛和算术基本定理快速求出某个数的i^N #include <bits/stdc++.h> using namespace std; using ll=long long; con 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Z_L_G
发表于 2025-07-24 10:50:00
#积性函数 #线性筛 #快速幂 题意 给定n，求解 n<=1.3e7 思路 满足积性函数 需要找到n以下每个数的n次方，可以用筛法，质数的用快速幂计算，合数的用质数递推 因为空间限制，无法记录每个数的最小质因子，但其实可以直接暴力的乘上每一个质因子，同时开一个bool的vis数组保证每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 andif
发表于 2023-10-01 00:03:01
NC23047 - 华华给月月出题 题意 给你一个, 让你求) 数据范围 思路 通过观察发现是积性函数，那么我们可以通过欧拉筛预处理出所有的 和其他预处理不同，因为空间的问题，我们不能再开一个数组来记录，每个数字第一个质因数出现的次数 接着观察可以发现，这个函数也是完全积性函数，那么我们就可以不维 展开全文
去ta的博客 赞 (0) 回复(1) 收起

问题信息

思维题
难度：
0条回答 16浏览

热门推荐

通过挑战的用户

查看代码

相关试题

华华给月月出题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号