网站运营介绍,常州住房和城乡建设局网站首页,建设一个网站所需要注意的,昆明做小程序的公司阅兵式 发布时间: 2017年6月25日 12:53 最后更新: 2017年7月3日 09:27 时间限制: 1000ms 内存限制: 128M 描述 阅兵式上#xff0c;将士们排成一个整齐的方阵#xff0c;每个将士面朝前方。问正中心的将士能向前看到几个将士#xff1f;注意#xff0c;一条直线上的将… 阅兵式 发布时间: 2017年6月25日 12:53 最后更新: 2017年7月3日 09:27 时间限制: 1000ms 内存限制: 128M 描述 阅兵式上将士们排成一个整齐的方阵每个将士面朝前方。问正中心的将士能向前看到几个将士注意一条直线上的将士会产生遮挡关系。 输入 多组输入数据不超过10000组。 每组数据一行一个正整数n表示方阵的大小。 数据满足n≤106n为奇数。 输出 每组数据输出一行一个正整数表示答案。 样例输入1 5 样例输出1 7 题解由于这个具有很强的对称性所以我们只看一个三角形区域就可以了把三角形区域的结果乘以4然后减去1就得到了总的答案。
三角形区域部分斜率的 种数计算方法如下
横坐标为1时候纵坐标为1:1种
横坐标为2时候纵坐标为1:1种
横坐标为3时候纵坐标为1、2:2种
横坐标为4时候纵坐标为1、3:2种
我们可以知道横坐标为x的时候共有phi(x)种。其中phi是欧拉函数
这样的话只需要对欧拉函数求一个前缀和就可以统计出三角形区域的斜率种数了
代码 #include stdio.h
#define MAXN 1000007
int minFactor[MAXN], phi[MAXN];
int prime[MAXN], primeNum;
long long sum[MAXN];
void calPhi()
{phi[1] 1;for (int i 2; i MAXN; i){if (!minFactor[i]){prime[primeNum] i;minFactor[i] primeNum;phi[i] i - 1;}for (int j 1;; j){int t i * prime[j - 1];if (t MAXN)break;minFactor[t] j;if (j minFactor[i]){phi[t] phi[i] * prime[j - 1];break;}phi[t] phi[i] * (prime[j - 1] - 1);}}
}
int main(){calPhi();int n;sum[1] 1;for(int i 2;i MAXN;i){sum[i] sum[i-1] phi[i];}while(~scanf(%d,n)){if(n 1){puts(0);continue;}int t n/2;long long res sum[t];//求 一个三角形 printf(%lld\n,4*res-1);}return 0;
}
