首页 > 代码库 > hdu 2051 Switch Game(模拟/数论)
hdu 2051 Switch Game(模拟/数论)
题目意思:
http://acm.hdu.edu.cn/showproblem.php?pid=2053
给你n个灯,刚开始全灭,问经过无穷多次操作后,求第n个灯的状态。
题目分析:
见代码注释。
AC代码:
/** *@xiaoran *应该是数论问题,先模拟看看(过了),现在来看这道题 *题意:给你n个灯,刚开始全灭,问经过无穷多次操作后,第n个灯状态 *对于第i次操作,改变所有i的倍数的状态 *发现当操作到n+1次之后肯定不会对n有影响,此题变为操作n次之后的n的状态 *下面分析:刚开始n的状态为0,如果对第n个灯操作了偶数次,其状态还是0, *操作奇数次变为1,现在来分析对于n:如果i是n的约数,就会改变n的状态,但是 *j=n/i也是n的约数,还会把n的状态改变回来,到这里可以发现当i=n/i的时候,才会 *对n的状态发生影响,刚开始n状态为0,如果n是个完全平方数,则会变为1. */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int a[100005]; int main() { int n; while(cin>>n){ int k=(int) (sqrt(n)+0.5); k*k==n?printf("1\n"):printf("0\n"); /**模拟 memset(a,1,sizeof(a)); for(int i=2;i<=n;i++){ for(int j=i;j<=n;j+=i){ a[j]=!a[j]; } } if(n==1) printf("1\n"); else printf("%d\n",a[n]); **/ } return 0; }
hdu 2051 Switch Game(模拟/数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。