[poj 3090]Visible Lattice Point[歐拉函數]

找出N*N范圍內可見格點的個數.

只考慮下半三角形區域,可以從可見格點的生成過程發現如下規律:

若橫縱坐標c,r均從0開始標號,則

(c,r)為可見格點 <=>r與c互質

證明:

若r與c有公因子1<b<min(r,c),則(c/b, r/b)在線段(0, 0)(c, r)上,則(c, r)不是可見格點.(充分性)

若r與c互質,顯然線段上不存在整點,則(c, r)不是可見格點.(必要性)

φ(n)表示不超過n且與n互素的正整數的個數，稱為n的歐拉函數值

也就是橫坐標增1後縱坐標合法數目,即新增可見格點數(下半三角形區域).用時應乘二.

#include<stdio.h>
#include<string.h>
#include<math.h>
int ans[1005];
//由歐拉公式
//phi(m) = m * (p1-1)/p1 * (p2-1)/p2 * .. * (pn-1)/pn. pi為大於1且不超過m的與m互質的數

int eular(int n)
{
    int s,i,m;
    m=(int)sqrt(n+0.5);//出於精度問題考慮,其實就是開根號向下取整
    s=n;
    for(i=2; i<=m; i++)
        if(n%i==0)//i是n的因數(如何保證是質數?看下文)
        {
            s=s/i*(i-1);//歐拉公式是連乘的,一項項乘
            while(n%i==0)
                n/=i;///去掉n中所有i因數,也就相當於篩掉了n中的i的倍數,使得此後i的倍數都不能整除"n"
        }///那麼下一個能夠整除n的i一定是質數
    if(n>1)
        s=s/n*(n-1);
    return s;
}
int main()
{
    int n,i,t,cas=1;
    scanf("%d",&t);
    ans[1]=3;
    for(i=2; i<=1000; i++)
        ans[i]=ans[i-1]+eular(i)*2;
    while(t--)
    {
        scanf("%d",&n);
        printf("%d %d %d\n",cas++,n,ans[n]);
    }
    return 0;
}

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int ans[MAXN];
int eular(int n)
{
    int i,s,m;
    m = (int)sqrt(n+0.5);
    s = n;
    for(i = 2;i <= m;i++)
    {
        if(!(n%i))
        {
            s = s / i * (i-1);
            while(!(n%i))
                n /= i;
        }
    }
    if(n>1)
        s = s / n * (n-1);
///假設n可以分解為(升序排列)p[1], p[2], .. p[n-1], p[n]那麼√n > p[n-1]
///反之 則 √n <= p[n-1]
///      => n <= p[n-1]*p[n-1] < p[n-1]*p[n] < p[1]*p[2]*..*p[n-1]*p[n] = n   矛盾
///因此,循環結束時,最多只剩下1個質因子.
    return s;
}

int main()
{
    int T;
    scanf("%d",&T);
    memset(ans,0,sizeof(ans));
    int last = 0;
    ans[0] = 1;
    for(int k=1;k<=T;k++)
    {
        int n;
        scanf("%d",&n);
        if(last>=n)
        {
            printf("%d\n",ans[n]);
            continue;
        }
        for(int i=last+1;i<=n;i++)
        {
            ans[i] = ans[i-1] + 2*eular(i);
           // printf("eular(%d) = %d\n",i,eular(i));
        }
        last = n;
        printf("%d %d %d\n",k,n,ans[n]);
    }
}