比赛 20160421s 评测结果 AATTTTTTTT
题目名称 数论函数簇 最终得分 20
用户昵称 Satoshi 运行时间 8.232 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2016-04-21 11:32:23
显示代码纯文本
#include <fstream>
//#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ifstream cin("functiona.in");
ofstream cout("functiona.out");
int gcd(int x,int y)
{
	while(true)
	{
		if(!x)return y;
		if(!y)return x;
		if(x>y)x%=y;
		else y%=x;
	}
}
int n;
int realmod(int x,int p)
{
	return (x%p+p)%p;
}
int F(int x)
{
	int a,b,c,tot=0,d,haha=0;
	int X,Y,sum;
	bool flag=0;
	//cout<<x<<' ';
	for(a=1;a<x;a++)
	{
		X=((ll)a*(a-1))%x;
		if(X)continue;
		//cout<<a<<' ';
		//haha++;
	    tot+=1+(x-1)/(x/gcd(a,x));
	}
	//cout<<endl;
	//cout<<haha<<endl;
	return tot;
}
void test()
{
	int i,sum=0;
	cin>>n;
	//cout<<F(n)<<endl;
	for(i=1;i<=n;i++)
	{
		//cout<<i<<' '<<F(i)<<endl;
		sum+=F(i);
		//cout<<sum<<endl;
	}
	cout<<sum<<endl;
}
int main()
{
	test();
	return 0;
}