标签归档:欧拉函数

UVA – 11426 GCD – Extreme (II)

题目链接

给数n,求出所有gcd(i,j) (i<j<=n)的和.

对两个互质的数i,j,即gcd(i,j)=1,给它们都添加一个因子2,则有gcd(2i,2j)=2. 于是有gcd(ki,kj)=k.
求出所有互质的数对,然后就能进一步求出题目所需要的结果了.

用欧拉函数求出i以内与之互质的数的个数,并打表记录s=i*j内所有的数对i,j的gcd和:
sum[i*j]+=j*phi[i]

最后弄个前缀和,就能快速查询结果了.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int phi[4000005];
long long sum[4000005];
void euler(int n){
  for(int i=2;i<=n;++i) phi[i]=i;
  for(int i=2;i<=n;++i){
    if(phi[i]==i){
      for(int j=i;j<=n;j+=i){
        phi[j]=phi[j]/i*(i-1);
      }
    }
    for(int j=1;i*j<=n;++j){
      sum[j*i]+=j*phi[i];
    }
  }
  for(int i=1;i<=n;++i){
    sum[i]+=sum[i-1];
  }
}

int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
  int n;
  euler(4000000);
  while(cin>>n&&n){
    cout<<sum[n]<<endl;
  }
  return 0;
}

POJ 3090-Visible Lattice Points


题目链接:POJ 3090

题意:
在\((0,0)\)为左下角,\((N,N)\)为右上角的矩形中,除了\((0,0)\)之外,每个点上都插着一个钉子,如下图所示.求在\((0,0)\)往四周看,能够看多少个钉子.一个钉子能被看到,当且仅当连接它和原点的线段上没有其他钉子.

题图

Solution:
除了\((1,0),(0,1),(1,1)\)这三个钉子外,一个钉子\((x,y)\)能被看到当且仅当\(gcd(x,y)=1\),即互质.并且观察可以发现,能看到的钉子关于\(y=x\)对称.于是可以只考虑一半,转化为求对于每个\(2<=x<=N\),有多少个y满足\(1<=y<x\)且\(gcd(x,y)=1\),即x的欧拉函数值. 可以通过Eratosthenes筛法求出\([2,y]\)中每个数的欧拉函数,也可以用线性筛法.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>

using namespace std;
#define MAX_N 2000000001

typedef long long ll;
typedef unsigned long long ull;

int phi[1005];

void euler(int n){
  for(int i=2;i<=n;i++) phi[i]=i;
  for(int i=2;i<=n;i++){
    if(phi[i]==i){
      for(int j=i;j<=n;j+=i){
        phi[j]=phi[j]/i*(i-1);
      }
    }
  }
} 

int main() {
  int T;
  cin>>T;
  euler(1000);
  int kase=0;
  while(T--){
    int n;
    cin>>n;
    int ans=3;
    for(int i=2;i<=n;i++){
      ans+=phi[i]*2;
    }
    printf("%d %d %d\n",++kase,n,ans);
  }
  return 0;
}