CodeForces 900D Unusual Sequences

题目链接: https://codeforces.com/contest/900/problem/D

题意

假设有distinct 正整数序列{a1,a2,,,an}，满足gcd(a₁, a₂, ..., a_n) = x ，且 ∑ai = y，那么求满足条件的序列的数目。

老题，一直没AC，今天算是明白了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 const ll mod=(ll)1e9+7;
 6 ll qPow(ll a,ll b,ll m)
 7 {
 8     ll ret=1ll;
 9     while(b){
10         if(b&1) ret=(ret*a)%m;
11         a=a*a%m;
12         b>>=1;
13     }
14     return ret;
15 }
16 
17 map<ll , ll> F;
18 ll getF(ll t){
19     if(F.count(t)){
20         return F[t];
21     }
22     ll ans=qPow(2ll,t-1,mod);
23     for(ll i=2ll;i*i<=t;++i){
24         if(t%i) continue;
25         ll j=t/i;
26         if(i!=j) ans=ans-getF(i)+mod-getF(j)+mod;
27         else ans=ans-getF(i)+mod;
28         ans%=mod;
29     }
30     ans=(ans-F[1]+mod)%mod;
31     F[t]=ans;
32     return F[t];
33 }
34 
35 int main(){
36     ios::sync_with_stdio(false);cin.tie(0);
37     ll XX,YY;
38     cin>>XX>>YY;
39     if(YY%XX){
40         cout<<0<<endl;
41     }
42     else{
43         ll tot=YY/XX;
44         F[1]=1ll;
45         cout<<getF(tot)<<endl;
46     }
47     return 0;
48 }

View Code