杭州本地网站,建设银行官网首页网站南山片区,网站建设公司seo关键词,深圳做小程序网站设计今天是贝茜的生日#xff0c;为了庆祝自己的生日#xff0c;贝茜邀你来玩一个游戏#xff0e;
贝茜让 N头奶牛#xff08;编号 11 到 N#xff09;坐成一个圈。
除了 11 号与 N 号奶牛外#xff0c;i 号奶牛与 i−1 号和 i1 号奶牛相邻#xff0c;N号奶牛与 11 号奶牛…今天是贝茜的生日为了庆祝自己的生日贝茜邀你来玩一个游戏
贝茜让 N头奶牛编号 11 到 N坐成一个圈。
除了 11 号与 N 号奶牛外i 号奶牛与 i−1 号和 i1 号奶牛相邻N号奶牛与 11 号奶牛相邻。
农夫约翰用很多纸条装满了一个桶每一张纸条中包含一个 11 到 10000001000000 之间的数字。
接着每一头奶牛 i 从桶中取出一张纸条纸条上的数字用 Ai 表示。
所有奶牛都选取完毕后每头奶牛轮流走上一圈当走到一头奶牛身旁时如果自己手中的数字能够被该奶牛手中的数字整除则拍打该牛的头。
牛们希望你帮助他们确定每一头奶牛需要拍打的牛的数量。
即共有 N 个整数 A1,A2,…,AN1,2,…对于每一个数 Ai求其他的数中有多少个是它的约数。
输入格式
第一行包含整数 N。
接下来 N 行每行包含一个整数 Ai。
输出格式
共 N 行第 i 行的数字为第 i头牛需要拍打的牛的数量。
数据范围
1≤N≤105, 1≤Ai≤106
输入样例
5
2
1
2
3
4输出样例
2
0
2
1
3
思路
如果两层循环枚举会超时。
我们可以记录每个数出现的次数然后找每种数出现的倍数时间复杂度为nlogn
代码
#define _CRT_SECURE_NO_WARNINGS #includeiostream #includecstdio #includecstdlib #includestring #includecstring #includecmath #includectime #includealgorithm #includeutility #includestack #includequeue #includevector #includeset #includemath.h #includeunordered_map #includemap using namespace std; #define LL long long const int N (int)1e6 5; const long long mod (LL)100003; #define rep(i,a,b) for (int i a; i b; i) #define per(i, a, b) for(int ia;ib;i--) int T; int n; int a[N], b[N], maxx, x, c[N]; int main() { cin n; rep(i, 1, n) scanf(%d, a[i]), c[a[i]]; rep(i, 1, 1e6) { for (int j i; j 1e6; j i) b[j] c[i]; } rep(i, 1, n) printf(%d\n, b[a[i]] - 1); return 0; }
