标签：AtCoder gcd Beginner 206 int long include SG define

AtCoder Beginner Contest 206（Sponsored by Panasonic）（E，F）

E（容斥，gcd)

E

这个题大意就是给出一个\(l\)和一个\(r\),寻找满足以下条件的一对数\((x,y)\)的数量

\(gcd(x,y)!=1\)

\(gcd!=x\)并且\(gcd!=y\)(从这一句我们可以知道\(x\)不可能被\(y\)整除)

那么我们可以设\(x\)是\(t\)的倍数，\(y\)是\(t\)的倍数，先保证\(gcd(x,y)\)不为\(1\),

对于\([l,r]\)这一个区间可以是\(t\)的倍数的最小的数是\(\frac{l-1}{t}\times t\),最大的那个倍数是\(\frac{r}{t}\times t\),所以我们可以很简单的求出这个区间是\(t\)的倍数的数量\(cnt\),然后我们要让\(gcd(x,y)\)是\(t\)不仅要都要是\(t\)的倍数（\(w^2\),两个都从里面选），还可能会有\(gcd\)是\(2t\)等的，所以我们要减去那些可能是其他\(t\)的倍数的\(gcd\)的情况，用\(f[t]\)表示\(gcd\)是\(t\)的一对数的数量，那么需要减去\(f[2t]\)等等

然后我们再考虑第二句话的要求，\(x\)和\(y\)之间不能存在整除的关系，那么我们手动减去那些整除的一些

对于此时的\(gcd\)为\(t\)时，假设\(x=t\),那么存在可以是\(x\)的倍数的数有\(\frac{r}{x}\)个，同样假如\(y\)为\(t\)时，同样也是这么多，但是当\((t,t)\)只有一个，这里多计算了一次，需要减一

参考

具体可以看代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=1e9+7;
int  n;
int f[maxn],l,r;
signed main() 
{
   cin>>l>>r;
   l--;
   int ans=0;
   for (int i=r;i>=2;i--)
   {
      int w=r/i-l/i;//(l-1)/i这个数最小的x*i>=l
      f[i]=w*w;
      for (int j=i+i;j<=r;j+=i)
      {
         f[i]-=f[j];
      }
      ans+=f[i];
   }
   for (int i=l+1;i<=r;i++)
   {
      if(i==1) continue;
      int now=r/i;
      now=now*2-1;
      ans-=now;
   }
   cout<<ans<<"\n";
   system ("pause");
    return 0;
}

F（博弈，SG，记忆化）

F

这个题大意就是一个游戏，每个人都可以选择一个区间段，只要这一个区间没有和之前已经选过的区间重合即可，如果这个人选不出，那么这个人就输了

对于这一道题，就是用了\(sg\)函数和一些记忆化来写的

对于\(sg\)函数什么时候该用，什么时候不该用，我还不是很懂，之前也做过一次题，不过是通过打表得出规律的

例题

感觉这个人的解释还蛮清楚的，学习

其中给出了一个公式

\[SG(x)=mex(SG(y)|x\rightarrow y) \]

然后我们可以变化一下，得到

\[SG(l,r)=mex(SG(l,ll)\bigoplus SG(rr,r)|SG(l,r)\rightarrow SG(l,ll)和SG(rr,r)) \]

有了以上公式其他的都很好写了

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=100+10;
const int mod=1e9+7;
int  n;
vector<int>g[maxn];
int dp[maxn][maxn];
int find(int l,int r)
{
   if(l>r) return 0;
   if(dp[l][r]!=-1) return dp[l][r];
   set<int>st;
   for (int ll=l;ll<=r;ll++)
   {
      for (auto rr:g[ll])
      {
         if(rr<=r)
         {
            int now=find(l,ll)^find(rr,r);
            st.insert(now);
         }
      }
   }
   int now=0;
   for (auto x:st)
   {
      if(now==x)
      {
         now++;
      }
      else 
      {
         break;
      }
   }
   dp[l][r]=now;
   return dp[l][r];
}
void solve()
{
   cin>>n;
   for (int i=1;i<=100;i++)
   {
      g[i].clear();
   }
     memset(dp, -1, sizeof(dp));
   for (int i=1;i<=n;i++)
   {
     int l,r;
     cin>>l>>r;
      g[l].push_back(r);
   }
   if(find(1,100)>0)
   {
      cout<<"Alice\n";
   }
   else 
   {
      cout<<"Bob\n";
   }
   return ;
}
signed main() 
{
   int t;
   cin>>t;
   while (t--)
   {
      solve();
   }
   system ("pause");
    return 0;
}

标签：AtCoder,gcd,Beginner,206,int,long,include,SG,define
From： https://www.cnblogs.com/righting/p/17386208.html