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

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

編輯：關於C++

題目顯然讓求φ（∏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++
abap alv multiple header using write

A standard SAP ALV list report
poj2559 Largest Rectangle in a Histogram

DescriptionA histogram is a po
筆試題21 . LeetCode OJ (8)

class Solution {public: int my
【C/C++學院】0903

boost模板庫與線性表Boost的安裝使用boost，首先
bzoj1996【HNOI2010】chorus 合唱隊

DescriptionInputOutputSample I
hdu2196 Computer（樹形dp）

ComputerTime Limit: 1000/1000

相關文章
閱讀排行榜
LeetCode 278 First Bad Version（第一個壞版本）（二分法）（*） leetcode筆記：Pow(x, n) Muduo 網絡編程示例（二） Boost.Asio 的聊天服務器 數據結構和算法14 之歸並排序 [LeetCode] Missing Number 打造自己的Windows終端服務客戶端 TForm常用技巧 C/C++源代碼書寫規范 [leetcode] 120 Triangle C++單元測試工具CppUnit使用簡介 C++流操作算子
熱門圖文
記錄asp.net網站是什麼原因導致停止運行的代碼 hibernate-在Hibernate中,用Query查詢好,還是用Hibernate臨時模版查詢好? datagrid綁定list沒有數據 表頭不顯示的解決方法 PHP 輸出緩沖控制(Output Control)詳解 C#頁面之間傳遞參數的幾種方法荟萃 簡單模擬 HDU 4749 c#中sqlhelper類的編寫(二)， PHP 讀取大文件程序代碼
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved