简单数学题
2021/8/27 23:10:52
本文主要是介绍简单数学题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意
对于一个正整数 \(N\),存在一个正整数 \(T\),使得 \(\frac{N-\frac{1}{2}T}{N-T}\) 的值是正整数。
请输出所有可能的正整数 \(T\)(按从小到大的顺序排列)。
对于 \(100 \ \%\) 的数据,\(N \leq 10^{14}\)
解题思路
考虑分解这个上面那个式子,设 \(k\) 为 \(\frac{N-\frac{1}{2}T}{N-T}\) 的值:
\[\frac{N-\frac{1}{2}T}{N-T}=k \]分数上下同乘 \(2\) 得:
\[\frac{2N-T}{2N-2T}=k \]设 \(x=N-T\),化简得:
\[\frac{x+N}{2x}=k \]然后等式两边同乘 \(2\),得:
\[\frac{2x+2N}{2x}=2k \]化简得:
\[\frac{N}{x}+1=2k \]\[\because k \ 为正整数且 \ 1 \ 为正整数 \]\[\therefore \frac{N}{x} \ 为正整数 \]\[\therefore x \ 为 \ N \ 的因子,即 \color{red}{\ N-T \ 为 \ N \ 的因子} \]\[又 \because 2k \ 是偶数且 \ 1 \ 是奇数 \]\[\therefore \frac{N}{x} \ 为奇数,即 \ \color{red}{\frac{N}{N-T} \ 为奇数} \]再看回原式:
\[\frac{N-\frac{1}{2}T}{N-T}=k \]\[\because T \ 为正整数且 \ N-T \ 为正整数 \]\[\therefore N-\frac{1}{2}T \ 为正整数 \]\[\therefore \color{red}{T \ 为偶数} \]综上所述:
\[N-T \ 为 \ N \ 的因子,\frac{N}{N-T} \ 为奇数且 \ T \ 为偶数 \]跑出所有因子判断即可。
时间复杂度 \(O(\sqrt{n})\)。
AC CODE
#include<bits/stdc++.h> using namespace std; #define int long long int n; int p[10000000], ans; void js(int x) { for(int i = 1; i <= sqrt(x); i ++) { if(x % i == 0) { if((x - i) % 2 == 0 && n / i % 2 == 1) p[++ans] = x - i; if(i * i != x && i != 1) { if((x - x / i) % 2 == 0 && n / (x / i) % 2 == 1) p[++ans] = x - x / i; } } } } signed main() { scanf("%lld", &n); if(n == 1) { printf("0"); return 0; } js(n); sort(p + 1, p + ans + 1); printf("%lld ", ans); for(int i = 1; i <= ans; ++i) printf("%lld ", p[i]); return 0; }
这篇关于简单数学题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现