• 題意：給你一串數字，讓人找出所有的字串（可不連續），使得該串的gcd（）>1，如果該串中有k個數，求出所有滿足該條件的字串的k*gcd（）的和。
• 思路：假設某一串的gcd（）的長度為n，gcd（）為i，則該字串的和為，經過化簡可以得到，這個時候會有重復的，我們要減去多加的，這個時候多加的比如這樣：2，4 ，8，我們把（4，8）的組合放在gcd（）為2的位置了，而實際gcd（4，8）=4，所以我們要減去相同的。

• #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <cstring> using namespace std; const int mod=1000000007; const int maxn=1000000+10; long long dp[maxn]; long long a[maxn]; int num[1000010]; long long b[maxn]; int main() {int n;cin>>n;int maxx=0;dp[0]=1;memset(num,0,sizeof(num));for(int i=1; i<=n; i++){int x;cin>>x;maxx=max(maxx,x);dp[i]=(2*dp[i-1])%mod;num[x]++;}long long ans=0;long long sum=0;for(int i=maxx; i>=2; i--){int temp=0;sum=0;for(int j=i; j<=maxx; j+=i){temp+=num[j];}if(temp==0) continue;sum=((long long)temp*dp[temp-1])%mod;for(int j=i*2; j<=maxn; j+=i){sum=(sum-b[j]+mod)%mod;}b[i]=sum;ans=(ans+((long long)i*sum)%mod)%mod;}cout<<ans%mod<<endl;return 0; }
  

總結

以上是生活随笔為你收集整理的Winter is here的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。