xtu oj 原根

回顾

• A+B III
• 问题 H: 三角数
• 问题 G: 3个数
• 等式 数组下标查询，降低时间复杂度
• 1405 问题 E: 世界杯
• xtu 数码串
• xtu oj 神经网络
• xtu oj 1167 逆序数（大数据）

---

杂

有一些题可能是往年的程设的题，现在搬到 c 语言题里面了，把一些 c++ 的代码改一下改成 c 的差不多就能过。有些程设的题可能是外国算法竞赛题翻译了一下拿过来的，所以写不出很正常，不要沮丧。（网上能搜到的程设的题解，笔者就不写了，我也不会写，有点无奈）

这里随便贴几个网上程设题解的链接

• xtu oj 问题 D: 拼图
• xtu oj 问题 H: 刷油漆
• xtu oj 问题 L: 奇偶数位
• xtu oj 问题 G: 完全平方数II
  这个题题目的名字改了一下，原来叫平方数
  

有时候搜题解的时候，可以搜一搜题号，好像有些题改了一下题目的名字

旧 oj ：需要用校园网才能访问

算了，不管那么多，现在就先把这题拿下！

这题好像我没啥思路，等我问下朋友搞清楚了继续写。先试一下，要是能写出来就不问了。写了一下直接超时了。

我把我的超时代码贴在这儿，不知道为啥超时了，感觉只有 O(n) 的时间复杂度，不至于超时的呀。注意下面不是正确代码。

#include<stdio.h>
#include<stdbool.h>int a[100010];int main(){int p;while(scanf("%d",&p)){for(int i=1;i<100010;i++){a[i]=0;}int g=2;for(int i=1;i<=p-1;i++){a[g]=1;g*=2;g%=p;}bool flag=false;for(int i=1;i<=p-1;i++){if(a[i]==0){printf("No\n");flag=true;break;}}if(flag==false){printf("Yes\n");}}return 0;
}

思路

哈哈哈，把代码发给朋友，他告诉我加一个 EOF过了，我的思路就是直接模拟题意，bool 数组用来判断当前这个数字是不是出现了，出现了就标记为 1 ，奥其实这里用布尔数组更加明确一些，就是下标表示的是出现的这个数字，然后每一次都要取模，不取模容易超出存储范围，这里可能需要注意一个数学知识，就是一边做乘法一边取模，和对计算的结果取模结果是同一个。

其他的好像没有什么需要注意的。

这个题虽然写出来了，但是还有一个题还是没写出来，明天我再写一写，写不出来再去问朋友，一定要解决。

c 语言代码

#include<stdio.h>
#include<stdbool.h>int a[100010];int main(){int p;while(scanf("%d",&p)!=EOF){for(int i=1;i<100010;i++){a[i]=0;}int g=2;for(int i=1;i<=p-1;i++){a[g]=1;g*=2;g%=p;}bool flag=false;for(int i=1;i<=p-1;i++){if(a[i]==0){printf("No\n");flag=true;break;}}if(flag==false){printf("Yes\n");}}return 0;
}