参考:​​​​​​错排公式 //#include<bits/stdc++.h>using namespace std;#define int long longint f( int n ){if( n==1 || n==0 ) return 0;if( n==2 ) return 1;return ( n-1 )*( f( n-1 )+f( n-2 ) );}sig

思路：由于收费是按最大因子收费，故拆成素数用的钱比较少（除自身外只有1），若本身是素数就不拆了，收费1元；若不是素数由于n是在10 ^8以内，故可根据哥德巴赫猜想：对于大于2的偶数可以拆成两个素数，对于大于7的奇数可以拆成3个素数；故先判断是否为偶数，若是偶数，拆成两个素数，收费两元；若不是偶数，分两种情况：1. n-2是素数，这样的话就可以拆成2和n-2（2比较特殊，一个是素数的偶数），花费两