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

3813: 奇數國|樹狀數組|歐拉函數淺析

編輯：C++入門知識

3813: 奇數國|樹狀數組|歐拉函數淺析


題目顯然讓求φ（∏i=lrai）

 
可以用線段樹維護一下乘積然後求逆元再求歐拉函數，用壓位的方法可以縮小60倍的常數。考慮一下樹狀數組的做法，因為只有60個質因子，所以可以開60個樹狀數組維護每一個質因子，最初維護了前綴的乘積然後T飛了。因為乘法比起加法還是比較慢的所以可以維護一個前綴的指數和，這樣就可以在BZOJ成功卡進最後一頁QAQ，然而UOJ的Extra Test還是過不了（應該是我寫的代碼太丑的原因吧。。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define mod 19961993
#define N 100001
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
int prime[66],inv[66],b[300],top;
int tr[61][N],n,Q,a[N],flag;
ll cal(ll x,ll y)
{
    ll ans=1;
    for(;y;x=x*x%mod,y>>=1)
        if(y&1)ans=ans*x%mod;
    return ans;
}
void change(int x,int y,ll v)
{
    for(;y
   

  1. 上一頁:
  2. 下一頁:
C++入門知識
SDUTOJ 1489 求二叉樹的先序遍歷

SDUTOJ 1489 求二叉樹的先序遍歷 #inclu
【vc】1_Windows程序內部運行機制，1_windows運行機制

【vc】1_Windows程序內部運行機制，1_window
OpenCV的幾個小技巧

申明：以下的小技巧，均為OpenCV2.4.2下驗證過
c++獲取sqlite3數據庫表中所有字段的方法，sqlite3字段

c++獲取sqlite3數據庫表中所有字段的方法，sqlit
C++ - 錯誤: &amp;quot; &amp;#39;strdup&amp;#39; was not declared in this scope &amp;quot;

錯誤: strdup was not declare
hdu 2540 遮擋判斷 判斷有多少根柱子的投影沒有被完全遮擋

遮擋判斷 Time Limit: 10000/3000
相關文章
閱讀排行榜
VC++中關於TCHAR,WCHAR,LPSTR,LPWSTR,LPCTSTR的解釋[轉載] LeetCode Spiral Matrix Scala：Enumeration hdu 5076 最小割靈活的運用 POJ 1260-Pearls（DP） c++十進制整數千位分隔符 C++ const用法小結 （歡迎大家拍磚） Hulu面試題解答——N位數去除K個數字 poj 2031 Building a Space Station(prim)(基礎) poj 3160 UVa 10048 - Audiophobia(Floyd, Kruskal)
熱門圖文
JAVA多線程實現的兩種方式，java多線程兩種方式 C++ lambda表達式，lambda表達式 xml-【求助】eclipse新導入的android項目不能生成R.java文件 設計模式之Facade——家庭篇 Java數據庫連接池的幾種配置方法(以MySQL數據庫為例)，數據庫連接mysql java怎麼定義一個二維數組？，java定義二維數組 淺談c++資源管理以及對[STL]智能指針auto_ptr源碼分析，左值與右值 js jquery mobile-jquery mobile<div data-role=collapsible>失效
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved