【GCD+MST】ABC210 E

雨点打透心脏的1/2处 2024-03-17 19:16 42阅读 0赞

**这道题告诉我们，一道题一定要去手摸样例，多造几个数据，然后找思路**

**很多时候，题目看错了，码完发现思路错了，调半天调不出来，思路一直在旧框架打转，这些情况都是不去考察实际情况导致的，模拟样例真的能告诉我们好多东西**

**尤其是思路在旧框架打转，手造小数据真的能启发很多思路**

**知道这个道理之后写题目最好形成模拟小数据的习惯，说不定CF真的上分了呢**

**CF很重要的两个思想就是模拟小数据和猜结论，毕竟是GuessForces(bushi**

**还有从特殊情况出发，特殊化条件等思想**

**然后总结的trick和算法是为了给思路导向，是为了归纳**

**归纳和特殊化相辅相成**

题意：

![10c8e066eaf84b52a394b5444a2d1cba.png][]

![1cd12b47300f4a6e9d3cd3d0a8b4631f.png][]

![bed2cf64454c4a788aa7e4c0d6e8279e.png][]

思路：

初看一定是没思路的，但是模拟一下小数据，思路很快就出来了

![91a79c0f737a492b97fc17bb69503181.jpeg][]

![46874d6c72f64bd599cf032195509e4f.jpeg][]

![6f5950e49cc34768a7d6dffca9b73e6f.jpeg][]

![c6d23e40eb454100b1e3e16493d13bb3.png][]

思路：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e6+10;
    const int mxe=2e6+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    struct ty{
    	int a,c;
    }p[mxn];
    
    int N,M;
    
    bool cmp(ty x,ty y){
    	return x.c<y.c;
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=M;i++) cin>>p[i].a>>p[i].c;
    	sort(p+1,p+1+M,cmp);
    	int ans=0;
    	for(int i=1;i<=M;i++){
    		int t=__gcd(N,p[i].a);
    		ans+=(N-t)*p[i].c;
    		N=t;
    	}
    	if(N!=1) cout<<-1<<'\n';
    	else cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[10c8e066eaf84b52a394b5444a2d1cba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a8a9b7dda32b45a28bc4a81401b75e13.png
[1cd12b47300f4a6e9d3cd3d0a8b4631f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/4ea348576d244332997d10ab4c734cf9.png
[bed2cf64454c4a788aa7e4c0d6e8279e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/08dbe3835284439e8c9ecdc0a9cf6d56.png
[91a79c0f737a492b97fc17bb69503181.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/10af6797b9b245d0aa6a24a5086399b3.png
[46874d6c72f64bd599cf032195509e4f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/9e44a85eaf0a4f94ab9a0c04fdfc4a96.png
[6f5950e49cc34768a7d6dffca9b73e6f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3fb20b2f641c4c7cba75b95c353a064b.png
[c6d23e40eb454100b1e3e16493d13bb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/f347eab1a47d48aeb4fe2841245455ba.png