【C++竞赛 C】yyy的数学公式
C++ 竞赛 数学公式
2023-09-14 09:03:47 时间
时间限制:1s 内存限制:32MB
问题描述
yyy遇到了一个数学问题如下:
S_n=∑F(i) 其中F(i)表示i的最大奇因数
yyy的数学非常好,很快就得到了结果。现在他把问题交给你,你能解决吗?
输入描述
第一行一个整数T(1≤T≤1000)表示数据组数。
对于每组数据仅仅一个整数n(1≤n≤〖10〗^9)。
输出描述
对于每组数据输出一行:一个整数S_n。
输入样例
2
1
4
输出样例
1
6
样例解释
F(1)=1,F(2)=1,F(3)=3,F(4)=1
【题目链接】:
【题解】
f[i] = i (i为奇数);
f[i] = f[i/2] (i为偶数);
则对于输入的n;
我们先算出1-n中奇数的和;
对于偶数;又转换成求sum(n/2)了;
然后再把1..n/2中的奇数全部加起来;
而1..n/2中的偶数又转换成求sum(n/2/2)了;
….
【完整代码】
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void rel(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void rei(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
const int MAXN = 1e5+100;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int n;
LL sum(LL x)
{
LL temp = 0;
temp +=(1+x)*(1+x)/4;
return temp;
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--)
{
LL n;
scanf("%I64d",&n);
LL ans = 0;
while (n)
{
if (n%2==0)
ans+=sum(n-1);
else
ans+=sum(n);
n=n>>1;
}
printf("%I64d\n",ans);
}
return 0;
}
相关文章
- java实现第二届蓝桥杯连通问题(C++)
- C++标准pdf 分享
- C/C++每日一练(20230329)
- AHP-层次分析法(C++源码,附详细注释和样例)
- C++语言:成功解决未定义标识符 "string"、未定义标识符 "cout"、“name”: 未知重写说明符
- C/C++中的abort、atexit、exit和_Exit
- 【 华为OD机试 2023】 最快到达医院的方法(C++ Java JavaScript Python)
- C++学习笔记10-面向对象
- VC++调用IcmpSendEcho函数实现对远端地址的ping检测(附源码)
- 学习 C++,关键是要理解概念,而不应过于深究语言的技术细节
- 【C++科学计算】解决“ARMADILLO_INCLUDE_DIR-NOTFOUND/armadillo_bits/config.hpp not found!”
- pytorch 5 pytorch模型转libtorch部署(C++)并读取图片测试
- 学习C++:C++进阶(五)CMake应用篇---集成第三方库和依赖管理