ACM – UVA10820 – 欧拉函数

点击量:31

给出一个Answer(x,y)函数,x,y属于[1,N],$Answer(kx, ky)$可以由Answer(x,y)得出,目的是求需要计算多少Answer(x,y)。

就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数,所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 1e5 + 10;
int phi[maxn];
void phi_table(int n)
{
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    for(int i = 2; i <= n; i++) if(!phi[i])
        for(int j = i; j <= n;j += i)
        {
            if(!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i-1);
        }
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int N;
    phi_table(maxn-1);
    ll ans;
    while(scanf("%d", &N), N)
    {
        ans =0;
        for(int i = 1; i <= N;i ++)
            ans += phi[i];
        ans = ans *2 - 1;
        printf("%lld\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注