TIOJ 1726 Dice Wars

  老實說 我這題真的AC得很莫名其妙
本來一點想法也沒有 然後用一些詭異的優化答案就出來了?!

先不管複雜度 說說中心思想

先開n個vector
然後若是第i個位置是k
那麼在第 k 個vector丟入i

若詢問為a,b

那麼就是將所有a所在的位置
都詢問離該點最近的 b 的位置(在b的vector做lower_bound)

所以這樣每步就會是 O( SZ(vec[a]) lg( SZ(vec[b]) ) )
很明顯若是 SZ(vec[a])>SZ(vec[b])
我們可以交換a,b 達到較好的複雜度

最後
有兩個小小技巧
1.
把所有已經回答的詢問存起來
要是以前已經問過 就可以直接回答
2.
如果有連續三個以上一樣的數字
中間的可以全部都不要存

然後我就不會算複雜度了
但是有一種構造方法可以弄成O(n*sqrt(n)*lg(n) )
就是共sqrt(n)個數字 每個數字有sqrt(n)個
詢問種類最多約 sqrt(n)*sqrt(n)/2
每個次詢問是sqrt(n) lg(n)
所以是O(sqrt(n)*sqrt(n)/2*sqrt(n)*lg(n))=O(n*sqrt(n)*lg(n) )

如果有神人會證複雜度務必告訴我

2018/3/8 補證明
我們已經知道每次詢問複雜度是O( SZ(vec[a]) lg( SZ(vec[b]) ) )
假設SZ(vec[a])<=SZ(vec[b])
考量下列兩種情形

1 . SZ(vec[a])<=sqrt(n)
　這時每次詢問都是O( sqrt(n) lg( n ) )
　總詢問q次　所以此部分詢問複雜度是O( q sqrt(n) lg( n ) )

2 . sqrt(n)<=SZ(vec[a])<=SZ(vec[b])
　我們知道大小大於sqrt(n)的vec，最多只有sqrt(n)個
　也就是說，要在此情形詢問vec[a]，最多只會問sqrt(n)次
　也就是說，對於vec[a]裡面每一個元素，最多只會問sqrt(n)次
　而總元素數量是n，所以總複雜度就是O( n sqrt(n) lg( n ) )

所以此題的複雜度就是O( (n+q) sqrt(n) lg( n ) )

#include <bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
typedef vector<int>::iterator iter;
//macro
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP1(i,a,b) for(ll i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
const int INF=1e9;
const ll MA=1e6+5;
const ll MOD=1e9+7;
//}}}
int n,m;
vector<int> v[60010];
map<pii,int> mp;
int arr[60010];
int main(){
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 int k;
 for(int i=1;i<=n;i++)
  cin>>arr[i];
 for(int i=1;i<=n;i++){
  if(arr[i-1]!=arr[i]||arr[i+1]!=arr[i])
   v[arr[i]].emplace_back(i);
 }
 int a,b;
 while(m--){
  cin>>a>>b;
  if(!SZ(v[a])||!SZ(v[b])){
   cout<<"-1\n";
   continue;
  }
  if(a==b){
   cout<<"0\n";
   continue;
  }
  if(a>b) swap(a,b);
  if(mp.find({a,b})!=mp.end()){
   cout<<mp.find({a,b})->second<< '\n';
   continue;
  }
  if(SZ(v[a])>SZ(v[b])) swap(a,b);
  int mi=INF;
  for(int i=0,si=SZ(v[a]);i<si;i++){
   int x=lower_bound(ALL(v[b]),v[a][i])-v[b].begin();
   if(x!=SZ(v[b])) mi=min(mi,v[b][x]-v[a][i]);
   if(x){
    x--;
    mi=min(mi,v[a][i]-v[b][x]);
   }
  }
  cout<<mi<< '\n';
  if(a>b) swap(a,b);
  mp[{a,b}]=mi;
 }
 return 0;
}

ZJ d374 X^2 ≡ 1 (mod M)

這是一個數學題

吧

總之模運算什麼的不提了

直接說兩個性質

一：

設F為M的一個因數

若X^2 ≡ 1 (mod M)

則X^2 ≡ 1 (mod F)

二：

若M為質數

X^2 ≡ 1 (mod M)

的X值

只有 1 和 M-1

根據性質二

若M是質數就可以直接回答

若不是質數

可以用一點點有技巧的枚舉

先找出M的因數中

大於等於sqrt(m)的最小的因數

設此數為F

可知

F>=sqrt(m)

先以F為基準

找出所有X^2 ≡ 1 (mod F) 的X  (X<F)

然後將所有找出來的數

枚舉加上kF (最多加M/F次)

看看是否符合 X^2 ≡ 1 (mod M)

若是就加到答案裡

至於複雜度我不會算XD

跪求神人解答

以下附code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,p,sq;
vector<ll> ans;
inline bool che(ll k){
 return k*k%m==1;
}
bool is_prime(){
 for(ll i=2;i<=sq;i++)
  if(m%i==0)
   return 0;
 return 1;
}
void solve(){
 ll fac=-1;
 for(ll i=sq;i>=2;i--)
  if(m%i==0){
   fac=i;
   break;
  }
 fac=m/fac;
 vector<ll> mia;
 mia.clear();
 for(ll i=1;i<fac;i++)
  if(i*i%fac==1)
   mia.push_back(i);
 for(ll i=0;i<m;i+=fac)
  for(ll j=0;j<mia.size();j++)
   if(che(i+mia[j]))
    ans.push_back(i+mia[j]);
}
void output(){
 cout<<ans.size()<<'\n';
 for(int i=0;i<ans.size();i++)
  cout<<ans[i]<<'\n';
}
int main(){
 cin>>m;
 // 先將一和二例外判掉
 if(m==1){
  cout<<"0\n";
  return 0;
 }
 else if(m==2){
  cout<<"1\n1\n";
  return 0;
 }
 sq=sqrt(m);
 if(is_prime()){ 
  cout<<"2\n";
  cout<<1<<'\n';
  cout<<m-1<<'\n';
  return 0;
 }
 solve();
 output();
}