SGU 169 Numbers (找规律)
题意:中文题,直接忽略。。。
析:先说说我的思路,我一看这个题第一感觉就是要找规律,要是挨着算,猴年马月都跑不完,更何况时间限制是0.25s,怎么找规律呢,我算了一下前10位,分别是8,1,1,3,1,1,4,1,1,3,然后我就觉得应该是113114循环再加一第一位是8,果然AC了。
然后结束后我看看了题解好像是算出来的,因为数很大又不是高精度,肯定是要找规律了,假设n有k位,分别从右往左a1,a2...ak,首先a1(也就是个位)肯定不是9(因为如果是9,那么n+1就有0了),所以呢n+1各位分别是a1+1,a2...ak,因为n mod P(n) = 0,所以n = s * a1 * a2 *...* ak,n+1 = t * (a1+1) * a2 *... * ak,即:
n+1 - n = 1 = [t*(a1+1) - s*a1] * a2 * a3 *...* ak。所以可以得出a2,a3,...ai都为1。所以 a1 | n, (a1+1) | (n+1), ("|"表示整除,不是按位或)。
并且a1要考虑8个值(1-8)。
a1 = 1时,很明显是可以的;
a1 = 2时,第一个肯定成立(因为是偶数),只要考虑(a1+1) | (n+1),也就是3能不能整除n+1,首先前k-1位都是1,所以只要考虑3|(k-1+3)就OK了;
a1 = 3时,a1+1 = 4, 很明显后缀是14的不能整除4,不成立;
a1 = 4时,同上;
a1 = 5时,a1+1 = 6,和判断3是一样的;
a1 = 6时,判断7|(n+1),我们总结知道只有当前面的k-1个1是6的倍数时,7|(n+1)才成立;
a1 = 7时,8不能整除118,不成立;
a1 = 8时,同上,不成立。
下面第一个是我的AC代码,另一个是题解的代码。
代码如下:
#include <iostream>
#include <string>
#include <cstdio> using namespace std;
typedef long long LL; int main(){
int n; scanf("%d", &n);
--n;
if(!n) printf("8\n");
else if(n % 6 == 0) printf("4\n");
else if(n % 3 == 0) printf("3\n");
else printf("1\n");
return 0;
}
题解代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; int main() {
int k;
scanf("%d", &k);
if(k == 1) {
printf("8\n");
return 0;
}
int cnt = 1;
if((k - 1) % 3 == 0) {
cnt += 2;
if((k - 1) % 6 == 0) {
cnt ++;
}
}
printf("%d\n", cnt);
return 0;
}
最新文章
- vim(vi)常用操作及记忆方法
- Add&;Delete WindowService
- linux云服务器mysql ERROR 2002 (HY000): Can’t connect to local MySQL server through socket ‘/tmp/mysql.sock’
- 安装Sql server 2008时出现sql server 2005 express tools failed 怎么办?
- MATLAB随机森林回归模型
- Win32中文件的操作
- sublime 前端开发工具
- BootStrap 智能表单系列 九 表单图片上传的支持
- Asp.net mvc 5 razor
- DDoS攻击及防御措施
- 保护url时效性和安全性的一种解决方案
- java泛型(二)、泛型的内部原理:类型擦除以及类型擦除带来的问题
- Linux 小知识翻译 - 「邮件服务器」
- Flask发送邮件
- ftp修改上传后目录、文件权限问题 aix
- 董事局主席董事长总裁首席执行官CEO总裁董事监事区别
- struts2中的session、request 、和action往页面中传值的方法
- ie9 form submit 请求参数问题替代办法
- java遍历http请求request的所有参数实现方法
- nodejs的优点