给素材网站做签约设计不想做了,h5开发环境,厦门有什么网站制作公司,爱站网是干什么用的文章目录1. 题目2. 解题1. 题目
链接#xff1a;https://ac.nowcoder.com/acm/contest/10166/C 来源#xff1a;牛客网
牛牛最近学会了异或操作#xff0c;于是他发现了一个函数 f(x)x⊕(x−1)f(x)x\oplus (x-1)f(x)x⊕(x−1)#xff0c;现在牛牛给你一个数 n#xff0c…
文章目录1. 题目2. 解题1. 题目
链接https://ac.nowcoder.com/acm/contest/10166/C 来源牛客网
牛牛最近学会了异或操作于是他发现了一个函数 f(x)x⊕(x−1)f(x)x\oplus (x-1)f(x)x⊕(x−1)现在牛牛给你一个数 n他想知道 ∑i1nf(i)\sum_{i1}^n f(i)∑i1nf(i) 的值是多少请你告诉他。
示例1
输入
4
返回值
12
备注:
1≤n≤10^92. 解题
先算出 10 以内的 f(x)
i f(i) S(i)
1 1 1
2 3 4
3 1 5
4 7 12
5 1 13
6 3 16
7 1 17
8 15 32 发现x奇数时f(x)1f(x) 1f(x)1; x偶数时f(x)2∗f(x/2)1f(x) 2*f(x/2)1f(x)2∗f(x/2)1 Sum(n)n2∗Sum(n/2);Sum(n) n2*Sum(n/2);Sum(n)n2∗Sum(n/2);
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* * param n int整型 * return long长整型*/unordered_mapint, long long m;long long Sum(int n) {// write code hereif(n 1) return 1;if(m.find(n) ! m.end()) return m[n];long long s n2*Sum(n/2);return m[n] s;}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
