SGU 246. Black & White(数论)
2024-09-20 06:10:54
题意:
有2*n-1个黑色和白色的珠子组成的环形项链,求至少需要多少颗黑色珠子才能使任意排列的项链中都存在两个黑珠间有n个珠子.
(2*n-1<=2^31-1);
Solution:
先分析n=5,n=7,n=9的情况.
当2*n-1=5,必须有两颗黑珠距离为1(较短的方向).
2*n-1=7,必须有两颗黑珠距离为2.
2*n-1=9,必须有两颗黑珠距离为3.
可以发现 对k=2*n-1,必须存在两颗黑珠的距离为l=(k/2-1)
假设问题的答案是ans,
我们先来求ans-1,即最多的不满足问题条件的黑珠数
假设已经放下了一颗黑珠子位于t。那么距离t+l的地方,t+l*2,t+l*3....这些位置我们可以连起来.显然在在环内每隔1个位置放黑珠能放最多.
有两种情况,一种是连起来的边只形成了一个环,那么ans-1=(2*n-1)/2,
另一种是形成了多个环,那么ans-1=len1/2+len2/2....+leni/2 ,leni为每个环的长度.
接下来就是数学问题,可以通过求2*n-1,和l的最小公倍数来判断和求出上面所需要的值.
#include <iostream> using namespace std;
int n, ans; int gcd( int a, int b )
{
return b == ? a : gcd( b, a % b );
}
int main()
{
cin >> n;
int k = ( n >> ) - ;
int d = gcd( n, k );
int m = n / d, t = n / m;
ans += t * ( m / );
n -= t * m;
ans += n / ;
cout << ans + << endl;
}
最新文章
- Java的异常处理
- 带你走进rsync的世界
- SQL Server 2008 下载及安装教程
- Linux的find命令
- PyQt 学习笔记1——自定义窗口框架
- 使用phantomjs实现highcharts等报表通过邮件发送
- poj3067
- 如何在 iOS 中解决循环引用的问题
- DreamWeaver文件保存时,提示";发生共享违例";问题的解决方法
- bzoj 1066 : [SCOI2007]蜥蜴 网络流
- angular ng-repeat数组中的数组
- 广义后缀树(GST)算法的简介
- 团队作业6--展示博客(Alpha版本)
- java中Queue简介
- Extjs 4.0 Window
- Android launcher 壁纸 wallpaper
- jQuery字母大小写转换函数
- Centos6.10 安装Python 2.7.16
- cef-3.2623 build on vs2013
- [BigData - Hadoop - YARN] YARN:下一代 Hadoop 计算平台
热门文章
- HDOJ/HDU 1087 Super Jumping! Jumping! Jumping!(经典DP~)
- Test2014-3-1 魅力值比较
- HOWTO: Setup XCode 6.1 to work with OpenCV3 libraries
- pathmunge /etc/profile
- 第十一章、认识与学习 BASH Bash Shell 的操作环境
- VirtualBox检查更新失败解决办法
- [置顶] 如何访问web文件夹之外的文件
- ueditor编辑器图片自定义存放目录及路径修改
- java版本 ueditor 在线编辑器 配置
- HTML里面Textarea换行总结