模拟题

链接：https://www.nowcoder.com/acm/contest/185/D 来源：牛客网 题目描述 Johnson和Nancy要在星光下吃晚餐。这是一件很浪漫的事情。 为了增加星光晚餐那浪漫的氛围，他拿出了一个神奇的魔法棒，并且可以按照一定的规则，改变天上星星的亮暗。 Johnson想考考Nancy，在他挥动魔法棒后，会有多少颗星星依旧闪耀在天空。他知道，Nancy一定会一口说出答案。 Nancy当然知道怎么做啦，但她想考考你！ Johnson先将天上n个星星排成一排，起初它们都是暗的。 他告诉他的妹子，他将挥动n次魔法棒，第i次挥动会将编号为i的正整数倍的星星的亮暗反转，即亮的星星转暗，暗的星星转亮。 Johnson想问Nancy，最终会有多少个星星依旧闪亮在天空。 输入描述: 一个整数n，含义请见题目描述。 输出描述: 一个整数ans，即n次操作后会有多少个星星依旧闪亮。 示例1 输入 复制 3 输出 复制 1 示例2 输入 复制 7 输出 复制 2 备注: 对于60%的数据：n≤2×106 对于100%的数据：n≤1018 我们首先用下面这个程序来打个表： #include #include using namespace std; int main() { int a[1000]; int n=3,m,j,k,i,T; for (n=1;n<=50;n++) { int ans=0; memset(a,0,sizeof(a)); for (i=1;i<=n;i++) { for (j=i;j<=n;j++) { if (j%i==0) { a[j]==1?a[j]=0: a[j]=1; } } } for (i=1;i<=n;i++) ans += a[i]; cout<<"