程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
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. 下一頁:
Copyright © 程式師世界 All Rights Reserved