程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3090 Visible Lattice Points 歐拉函數

POJ 3090 Visible Lattice Points 歐拉函數

編輯：C++入門知識

POJ 3090 Visible Lattice Points 歐拉函數


 

題意：在坐標系中，從橫縱坐標 0 ≤ x, y ≤ N中的點中選擇點，並且這些點與（0,0）的連點不經過其他的點。

思路：顯而易見，x與y只有互質的情況下才會發生（0,0）與（x,y）交點不經過其他的點的情況，對於x,y等於N時，可以選擇的點均為小於等於N並且與N互質的數，共Euler(N)個，並且不重疊。所以可以得到遞推公式aa[i]=aa[i]+2*Euler(N)。
代碼：

 

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define maxn 10005
#define INF 0x7fffffff
#define eps 1e-8
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int aa[1005];
int Euler(int tot)
{
    int num=tot;
    for(int i=2; i<=tot; i++)
    {
        if(tot%i==0)
            num=num/i*(i-1);
        while(tot%i==0)
            tot/=i;
    }
    return num;
}
void init()
{
    aa[0]=0;
    aa[1]=3;
    for(int i=2; i<=1000; i++)
        aa[i]=aa[i-1]+Euler(i)*2;
}
int main()
{
    int T;
    scanf(%d,&T);
    init();
    for(int ii=1; ii<=T; ii++)
    {
        int tot;
        scanf(%d,&tot);
        printf(%d %d %d
,ii,tot,aa[tot]);
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
C++入門知識
ConcurrentHashMap的關鍵部分解析

ConcurrentHashMap是線程安全且高效的H
雙向鏈表（C++實現），實現

雙向鏈表（C++實現），實現 ///////////////
C++ 學習之旅 Windows程序內部運行原理

學習C++與.net不同的是，一定要搞清楚Windo
UVA - 1393 Highways

UVA - 1393 Highways Descript
最長公共子序列（動態規劃）

最長公共子序列（動態規劃） #include #incl
QML官方教程——Qt Quick Layouts Overview

附網址：http://qt-project.org/d
相關文章
閱讀排行榜
C++拷貝構造函數 bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]畢業旅行，bzojctsc2008 poj 1721 CARDS(置換) C++文件操作（1） Bill學C++ 第二季之mutable 的關鍵字 再談poj2255_解題報告 數據結構實驗 單鏈表 poj1463-1A 杭電 1203 I NEED A OFFER! POJ 3254 Corn Fields [狀壓DP] 游戲中的資源管理部分的設計(C++語言描述)
熱門圖文
網頁教學網收集20個方便網頁開發的工具 [問題貼]小白請教幾個關於Java虛擬機內存分配策略的問題，java虛擬機 2016弱校聯盟十一專場10.2---Around the World（深搜+組合數、逆元），201610.2---around ASP.NET中最簡單的自定義控件 android studio和genymotion安卓入門從零開始-0，genymotion安卓 poj 2955 Brackets(區間DP求最長匹配子串) visual studio-VS2013中未找到標識符 提高php運行速度的一些小技巧分享
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved