Topcoder SRM 697题解

---

D1L1

• 分子分母同乘a[i]:
  \(a_{i}^{b_{i}+1} mod \prod a_i = 0\)
• 然后我们考虑质因子p,设质因子p在a[i]中出现cnt[i]次
• 所以对于每个i都满足：`\(\sum (b_i+1)cnt_i >= \sum cnt_i\)
• \(\sum \frac{1}{b_i+1} > 1\)有解
• \(\sum \frac{1}{b_i+1} = 1\)时,b[i]满足两两不等有解。

#include 
    
     #include 
     
      #include 
      
       using namespace std;int gcd(int x, int y) {    return y==0?x:gcd(y,x%y);}int lcm(int x, int y) {    return x*y/gcd(x,y);}struct DivisibleSetDiv1 {    string isPossible(vector
       
         b) {        int sum = 1;        set
        
          st;        for (auto x: b) {            x ++;            sum = lcm(sum, x);            st.insert(x);        }        int s = 0;        for (auto x: b) {            x ++;            s += (sum / x);        }        if (s < sum)            return "Possible";        if (s == sum && st.size() == b.size())            return "Possible";        return "Impossible";     }} T;
        
       
      
     
    

D1L2

做法

• 一个有趣的算贡献问题

首先答案可以这么算

我们来采访第miao号选手，答案可以这么算

int ans=0;for i=0 to 1<

当然，也可以这么算

int ans=0;for x=0 to n:    for y=0 to n:        for i=0 to 1<

超进化！

int ans=0;for x=0 to n:    for y=0 to n:        ans += 有多少个i符合要求呢？

• 注意到a^x与b^x大小关系，由x在a,b在二进制下，不相等的最高位上，是0，还是1来决定。

Trie树！决定就是你了

#include 
    
     using namespace std;typedef long long LL;const int N = 200000+10;const int MOD = 1000000007;int n, m;int a[N];int ch[N*32][2],sum[N*32],size;void insert(int s) {    int now=0;    for(int i=m-1;i>=0;i--) {        int bit=(s>>i)&1;        if (!ch[now][bit]) {            ch[now][bit] = ++size;        }        now = ch[now][bit];        sum[now] ++;    }}LL cnt[30];LL cac(int s) {    int now=0;    for(int i=m-1;i>=0;i--) {        int bit=(s>>i)&1;        cnt[i]=sum[ch[now][bit^1]];        now = ch[now][bit];    }    LL ans=0;    ans = (LL)(n-1)*(n-1)%MOD*(1LL<<(m-2))%MOD;    for (int i=0;i
     
      >m>>n>>a>>b;    cout<
      
       <