歐拉函數 - HDU1286

歐拉函數的作用:

有[1,2.....n]這樣一個集合,f(n)=這個集合中與n互質的元素的個數。歐拉函數描述了一些列與這個f(n)有關的一些性質,如下:

1、令p為一個素數,n = p ^ k,則 ? f(n) = p ^ k - p ^ (k-1)

2、令m,n互質,則 ? f(m*n) = f(m) * f(n)

3、如果n為奇數,則 ? ?f(2 * n) = f(n)

?

下面給出一個例題的代碼,例題鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1286

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <string>
 7 #include <cmath>
 8 using namespace std;
 9 const int maxn = 32769;
10 
11 int ans[maxn],prim[4000],flag_p[maxn];
12 /*
13 把1~maxn所有的素數打出來 
14 */
15 int SolPrim()
16 {
17     memset(flag_p,0,sizeof(flag_p));
18     for(int i = 2;i < sqrt((double)maxn);++i)
19         for(int j = i * i;j < maxn;j += i)
20             flag_p[j] = 1;
21     int  f = 0;
22     for(int i = 2;i < maxn;++i)
23         if(!flag_p[i])
24             prim[f++] = i;
25 }
26 /*
27 打表,把結果全部打出來 
28 */
29 void PreSol()
30 {
31     int f = SolPrim();
32     memset(ans,0,sizeof(ans));
33     for(int i = 1;i < 32768;++i)
34     {
35         int temp = 1,t = i;
36         for(int j = 0;prim[j] <= i;++j)
37         {
38             int tt =  0;
39             while(t % prim[j] == 0)
40             {
41                 t /= prim[j];
42                 tt++;
43             }
44             if(tt) temp *= (pow(prim[j],tt-1) * (prim[j] - 1));
45         }
46         ans[i] = temp;
47     }
48 }
49 
50 int main()
51 {
52     PreSol();
53     int T,n;
54     scanf("%d",&T);
55     while(T--)
56     {
57         scanf("%d",&n);
58         printf("%d\n",ans[n]);
59     }
60     return 0;
61 }
View Code

?

轉載于:https://www.cnblogs.com/xiaxiaosheng/p/4713977.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/258513.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/258513.shtml
英文地址,請注明出處:http://en.pswp.cn/news/258513.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

其中一個頁簽慢_渭南提升一個大專學歷的有效方法

渭南提升一個大專學歷的有效方法&#xff0c;宏德教育&#xff0c;目前已形成以高等學歷教育為特色王牌&#xff0c;職稱考評、企業內訓為輔助的強力優勢品牌。渭南提升一個大專學歷的有效方法&#xff0c; 獲得發明專利或實用新型專利&#xff0c;且已實施取得效益。出版本專業…

《收集蘋果》 動態規劃入門

問題描寫敘述 平面上有N*M個格子&#xff0c;每一個格子中放著一定數量的蘋果。你從左上角的格子開始&#xff0c;每一步僅僅能向下走或是向右走&#xff0c;每次走到一個格子上就把格子里的蘋果收集起來&#xff0c;這樣下去&#xff0c;你最多能收集到多少個蘋果。 輸入&…

Xamarin XAML語言教程通過ProgressTo方法對進度條設置

2019獨角獸企業重金招聘Python工程師標準>>> Xamarin XAML語言教程通過ProgressTo方法對進度條設置 在ProgressBar中定義了一個ProgressTo方法&#xff0c;此方法也可以用來對進度條當前的進行進行設置&#xff0c;ProgressTo與Progress屬性的不同之處在于ProgressT…

Radar Installation

題目鏈接&#xff1a;http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id27586 題意&#xff1a; 在海岸線上擺放雷達并限定雷達覆蓋半徑d&#xff0c;再以海岸線為軸&#xff0c;給定海上島嶼坐標&#xff0c;求至少需要多少雷達可以覆蓋所以島嶼&#xff0c;如…

win7 + vs2015+ matlab2016a + python3.5安裝matcaffe cpu版本

參考&#xff1a; 1. caffe-windows直接安裝版---編譯后的Release 2.安裝Windows10 和環境下的caffe&#xff08;新版&#xff09; 3.win10vs2015編譯caffe的cpu debug版本、部署matcaffe 主要的方法參考文獻3. 當前caffe-windows僅支持python2.7和3.5 要注意的是&#…

python調用 matlab庫_python調用matlab的搜索結果-阿里云開發者社區

2018python技術問答集錦&#xff0c;希望能給喜歡python的同學一些幫助小編發現問答專區中有很多人在問關于python的問題&#xff0c;小編把這些問題匯總一下&#xff0c;希望能給喜歡python的大家一些啟示和幫助本帖不定期更新&#xff0c;喜歡的可以收藏哦python可能替代Java…

h5新特性

 CSDN博客 Gane_ChengHTML5新特性淺談 發表于2016/10/17 21:25:58 7809人閱讀 分類&#xff1a; 前端 轉載請注明出處&#xff1a; http://blog.csdn.net/gane_cheng/article/details/52819118 http://www.ganecheng.tech/blog/52819118.html &#xff08;瀏覽效果更好…

打勾顯示輸入的密碼 --EditText與setTransformationMethod

實現目標: 實現原理: 為CheckBox添加一個監聽器事件; 實現的源碼: package edu.cquptzx.showPassword; import android.app.Activity; import android.os.Bundle; import android.text.method.HideReturnsTransformationMethod; import android.text.method.PasswordTransforma…

mysql日期截取年月_攝影大賽丨“我遇見最美的光”第五屆全國醫務人員攝影大展 截稿日期2020年8月15日...

截稿日期2020年8月15日《“我遇見最美的光”第五屆全國醫務人員攝影大展》欣賞過山川壯麗&#xff0c;瞻仰過造化旖旎&#xff0c;敬重于生命偉大&#xff0c;感動于英雄凱旋……由《大眾攝影》主辦&#xff0c;正大天晴藥業集團股份有限公司、《中國衛生影像》雜志協辦的“我遇…

iframe子頁面內刷新父頁面中另一個iframe子頁面

框架頁面如下&#xff1a; <div id"aa" style"float: left; height: 500px; border-right-style: solid; border-right-color: #CCCCFF; border-right-width: 2px;"> <IFRAME id"tree" name"tree" src"/ScienProject…

Pytorch的C++接口實踐

Pytorch1.1版本已經提供了相對穩定的c接口&#xff0c;網上也有了眾多的資料供大家參考&#xff0c;進行c的接口的初步嘗試。 可以按照對應的選項下載&#xff0c;下面我們要說的是&#xff1a; 如何利用已經編譯好的官方libtorch庫和其他的opencv庫等聯合編寫應用&#xff1f…

一次慘痛的裝機經歷

最近不小心把我的聯想一體機電腦系統搞壞了&#xff0c;就不得不重裝系統&#xff0c;之前的系統是win7&#xff0c;于是開始的時候想著直接裝win10&#xff0c;升級一下系統。但是裝的過程中總是卡在了win10的正在準備系統中&#xff0c;進度環不轉了。后來轉了多次都不行&…

unity讓對象作為參數_unity-container – 一個unity容器可以將自身的引用作為構造函數參數傳遞嗎?...

簡短的答案是肯定的。當您使用Resolve方法時&#xff0c;這應該自動傳遞。例如&#xff1a;IUnityContainer container new UnityContainer();var something container.Resolve();另外&#xff0c;如果您想查看&#xff0c;這與Prism(CodePlex)使用的技術相同。更新增加測試&…

KnockoutJS + My97DatePicker

如何將Knockoutjs和其他腳本庫結合使用&#xff1f;這里給出一個Knockoutjs與my97datepicker配合使用的例子&#xff0c;例子中使用了ko的自定義綁定功能&#xff1a; ko.bindingHandlers.my97DatePicker {init: function (element, valueAccessor) {$(element).on(click, fun…

HttpClient v4.5 簡單抓取主頁數據

由于工作原因&#xff0c;需要每隔半小時刷新一些網頁&#xff0c;并查看上面的數據是否有更新。這件事能否自動化進行呢&#xff1f;查找了下Java相關的資料&#xff0c;蹦出一個關鍵詞&#xff1a;HttpClient。 HttpClient是常用Http客戶端庫&#xff0c;相關的資料也不少&am…

matlab局部放大的圖中圖畫法

【親測有效】 在作圖過程中&#xff0c;如果想將局部信息展示出來并且畫在同一張圖中&#xff0c;一般的MATLAB作圖法就比較拙計了&#xff0c;好在MATLAB還是很強大的&#xff0c;當然&#xff0c;除了不能當女朋友之外 .... ╮(╯▽╰)╭ function showdetail()% 在當前的ax…

進入Python世界——Python基礎知識

本文通過實例練習Python基礎語法, python版本2.7 # -*- coding: utf-8 -*- import randomimport re import requests from bs4 import BeautifulSoup# 爬取糗事百科的首頁內容 def qiushibaike():content requests.get(http://www.qiushibaike.com/).contentsoup BeautifulS…

db2 版本發布歷史_數據庫各廠商的發展歷史(2. DB2 of IBM)

如若轉載&#xff0c;請務必注明出處&#xff0c;iihero 2008.9.26于CSDN1973年&#xff0c;IBM研究中心啟動System R項目&#xff0c;為DB2的誕生打下良好基礎。System R 是 IBM 研究部門開發的一種產品&#xff0c;這種原型語言促進了技術的發展并最終在1983年將 DB2 帶到了商…

android---簡單的通訊錄

遺留問題:獲取頭像及其他信息 利用adapter和Cursor來獲取聯系人的姓名和手機號,重在復習之前學過的內容加深自己的理解. 其中需要注意的部分: 1.adapter中的getview的優化問題,用到tag這一屬性 2.onBackPressed()返回方法的重寫,使得程序更加人性化 下面是主要代碼 1.adapte…

win phone 獲取并且處理回車鍵事件

參考自&#xff1a;http://www.cnblogs.com/mohe/archive/2013/03/18/2966540.html 實用場景,比如輸入帳號和密碼啦,輸入搜索關鍵字啦.protected override void OnKeyDown(KeyEventArgs e) {if (e.Key Key.Enter){MessageBox.Show("我是windows phone 回車鍵"); …